Dynamic programming solution to the subset-sum decision problem
Posted
by Gail
on Stack Overflow
See other posts from Stack Overflow
or by Gail
Published on 2010-04-15T15:54:31Z
Indexed on
2010/04/15
16:23 UTC
Read the original article
Hit count: 334
Filed under:
computer-science
|homework
How can a dynamic programming solution for the unbounded knapsack decision problem be used to come up with a dynamic programming solution to the subset-sum decision problem? This limitation seems to render the unbounded knapsack problem useless.
In the unbounded knapsack, we simply store true or false for if some subset of integers sum up to our target value. However, if we have a limit on the frequency of the use of these integers, the optimal substructure at least appears to fail. How can this be done?
© Stack Overflow or respective owner
