HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Finding all solutions to subset sum for integers with bounded weights

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
allwithweightsfindingintegerssolutionsforsumboundedsubset

Problem

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)?

Solution

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.

Context

StackExchange Computer Science Q#7874, answer score: 4

Revisions (0)

No revisions yet.