4 ms·
Here'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 toy
by nroets 5y ago
Here'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...