3 ms·
If the values are small enough. The problem is that the length of the unary form grows exponentially
by hackcasual 5y ago
If the values are small enough. The problem is that the length of the unary form grows exponentially
- nroets 5y agoHere's that runs in O(√2^n) time and space. And with careful implementation it will never be significantly slower than the above DP algorithm. 1. Spilt the toys in two sets (A and B) of similar size. 2. Generate a sorted list L of all the possible sums that can be made with the toys in set A. If two sums are equal, keep only one. 3. Generate a sorted list M of all the possible sums that can be made with the toys in set B. If two sums are equal, keep only one. 4. Iterate through L forwards and through M backwards looking for two sums that together make up the target amount.
- H8crilA 5y agoThe lists L and M have to be O(2^N) in size, where N is the target sum. I fail to see how this is any faster. In fact I think it's a little slower, if N is the target sum and M is the number of toys this algorithm runs in O(2^N * M * log(M))
- nroets 5y agoNo. Small n in only 21. You split the toys in a set of 10 and a set of 11. What I'm really describing is the Meet In The Middle algorithm: https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-m...