4 ms·
I'm not understanding the "fill it from left to right with true on the specific amount of cents [and if it fits perfectly, you found a solution]." Isn't finding
by akersten 5y ago
I'm not understanding the "fill it from left to right with true on the specific amount of cents [and if it fits perfectly, you found a solution]." Isn't finding that "specific amount of cents [e.g. which choice of items achieves that amount]" the crux of the problem here that is glossed over? How would you test each combination to fit this boolean array without trying all of them brute force?
- jtsiskin 5y agoStart by only considering the Yo Yo, that is easy to fill out. Now consider both the Yo Yo and Doll, that is also easy to fill out given the current array. Then continue.
- H8crilA 5y agoHmm, true, addition is commutative, so you can reorder the elements however you want. Though it doesn't change the O() complexity you may get some performance tuning by starting with the largest elements. If we're at fine-tuning, one thing you can do is divide all numbers by the GCD of all numbers, assuming that the GCD is not just 1.
- H8crilA 5y ago$0.00 is always achievable (choose nothing), and negative values are never achievable. Is $0.01 achievable? Well, take all items, subtract their price from $0.01 and see if any of the results are achievable. If so, $0.01 is achievable. Repeat for $0.02, $0.03, ... This works because by the time you're processing $X you already know the answers to all values smaller than $X (and no item has a negative price).