Sum Finder
We are given the set of numbers S={5,8,2,4,6}. Our goal is to determine if 17 can be obtained as a sum of a subset of S. While this can be determined by a brute-force attack, the goal is to use a dynamic programming approach.
We enumerate the elements of S as a0,a1,...,a4. Let M be a 5-by-18 binary matrix such that M[i,j]=1 if some subset of {a0,...,ai} sums up to j, otherwise M[i,j]=0.
It is clear that M[i,0]=1 for all i and M[0,j]=0 for j=a0 and M[0,a0]=1.
From the definition of M, if follows that, for i>0:
M[i,j]=M[i−1,j] if 0<j<ai,
M[i,j]=1 if j=ai, and
M[i,j]=max{M[i−1,j],M[i−1,j−ai]} if 17>j>ai.
The last equality is determined by the following idea. If M[i−1,j]=1, then j can be formed as a sum of a subset of {a0,...,ai} that does not include ai. If M[i−1,j−ai]=1, then j can be formed as a sum of a subset of {a0,...,ai} that does include ai. If M[i−1,j]=M[i−1,j−ai]=0, then there is no way to form j as a sum of a subset of {a0,...,ai}.
Following the rules above, we give a complete characterization of M as follows:
(ai,j) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
---|
5 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
2 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
4 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
6 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Since M[4,17]=1, we see that 17 can be formed as a sum of a subset of S. Futhermore, the chart above can used to see that 17=4+8+5.