3 ms·
That the general problem is NP-complete does not mean that it's difficult to solve all the possible inputs. Sometimes to get a long run time, you need to constr
by gus_massa 5y ago
That the general problem is NP-complete does not mean that it's difficult to solve all the possible inputs. Sometimes to get a long run time, you need to construct an evil example on purpose.
For example, if you have 1000 slots for numbers, make 3 of them with the last digit equal to 1, and the rest with the last digit equal to 0, and the expected sum a number where the last digit is 1. In this case, it's equivalent to asking that the algorithm choose exactly one of the slots with a number where the last digit is 1.
Now do something similar with the second to last digit. And now with the third to last...
You can select a lot of sets of 3 slots of the 1000 slots, and use this encoding to force the algorithm to choose exactly one in each one. The problem is that you need a lot of digits to use this encoding.
But you are selecting numbers with 4 bytes, so you have only like 10 digits. With a better encoding, you can get like 16 conditions.
How nasty can be an example with only number of 4 bytes? I'm not sure, but I think they are nos nasty enough. You should look for examples that are constructed on purpose to be difficult to solve. (I tried googling one, but I failed.)
> Some other interesting notes: - Goal=150: Set=(1...100), there are 19,378,091 subsets that sum to 150 (94 seconds to compute)
When the goal is small enough, there are some dynamic programing trics that are very fast. https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... The problem is difficult to solve when the number is huge and the sum is also huge.