2 ms·
You 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
by gizmo686 5y ago
You 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?