4
$\begingroup$

Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer. I am interested in determining all subsets (not just one, and not just the number of them) of $W$ with a fixed sum $s$. I realize this is obviously NP-hard, but are there some efficient ways (e.g. dynamic programming) to obtain this result for these relatively nice conditions (e.g. only 50 items, weights integer and bounded)?

$\endgroup$
3
$\begingroup$

The dynamic programming algorithm can be adapted to give all solutions. You create a table $A$. The cell $A_{k,w}$ contains enough information to enumerate all subsets of $\{w_1,\ldots,w_k\}$ summing to $w$. When $k = 0$, this is trivial. Given $A_{k-1,\cdot}$, $A_{k,w}$ points at the two cells $A_{k-1,w},A_{k-1,w-w_k}$ (if they exist). The second pointer is also annotated with $w_k$. If you look at $A_{50,W}$, you can reconstruct all subsets by considering all paths going all the way to $A_{0,0}$. This can be done using a simple recursive procedure.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Yes, there is. Have a look at: http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ However, this seems to only give the existence of such a subset -- whereas, I am interested in determining all such subsets. Do you have an idea of how I could modify it to obtain that? $\endgroup$ – Bob S. Jan 10 '13 at 21:10
  • 1
    $\begingroup$ You will create an array (2-D). There you can find what you are looking for ("stepping back"). There is a rich material of this problem on the internet. Just google subset sum dynamic programming. $\endgroup$ – AJed Jan 10 '13 at 22:36
-1
$\begingroup$

Look at the coin change problem. Solutions are known which will give all results. If you have a problem with it, I can provide some code.

See http://www.algorithmist.com/index.php/Coin_Change for example

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The coin change problem that you refer to, especially the 3 variants mentioned in the link you provide, all can use the same coin multiple times. This is not the case in the question. The question is the subset sum problem, even if this too can be solved using dynamic programming. $\endgroup$ – Paresh Feb 10 '13 at 9:50
  • $\begingroup$ That's not the problem same. $\endgroup$ – jonaprieto Feb 26 '13 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.