2 ms·
The thing is that it being an instance of an NP complete class of problems means that there isn't a guarantee that there is an easy way to find a solution. Mean
by jameshart 5y ago
The thing is that it being an instance of an NP complete class of problems means that there isn't a guarantee that there is an easy way to find a solution. Meaning, you might have to check every combination - and even if you know there's a valid solution, there's no specific heuristic you can apply in searching the solution space that guarantees that it won't be the very last combination you try.
In particular, notice that the question asks 'is your solution the only one?'
Is there any way, in general, to know you've found all possible valid solutions to this problem without enumerating every single one?
- gizmo686 5y agoYou can prune entire sets of the combination space without needing to enumerate through all of them. One of the simplest such optimizations would be to set that if set S costs more than the target, then no superset of S is a valid solution.
- tsimionescu 5y agoSure, but that doesn't change the fact that there is no polynomial time algorithm for solving this problem. Your observation makes the problem possible to solve using backtracking (as otherwise there would be an infinity of combinations to check, since we can take multiples of a toy), but does not guarantee it can be solved in a reasonable time.
- jameshart 5y agoThe problem of finding all the subsets whose value exceeds the limit isn’t necessarily any easier than finding all the subsets whose value equals the limit, is it?