Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Project: MAT 1630
Views: 195
Kernel:

Sum Finder

We are given the set of numbers S={5,8,2,4,6}.S = \{5, 8, 2, 4, 6\}. Our goal is to determine if 1717 can be obtained as a sum of a subset of SS. While this can be determined by a brute-force attack, the goal is to use a dynamic programming approach.

We enumerate the elements of SS as a0,a1,...,a4.a_0, a_1, ..., a_4. Let MM be a 5-by-18 binary matrix such that M[i,j]=1M[i,j]=1 if some subset of {a0,...,ai}\{a_0,...,a_i\} sums up to j,j, otherwise M[i,j]=0.M[i,j]=0.

It is clear that M[i,0]=1M[i,0]=1 for all ii and M[0,j]=0M[0,j]=0 for ja0j\neq a_0 and M[0,a0]=1.M[0,a_0]=1.

From the definition of M,M, if follows that, for i>0i>0:

M[i,j]=M[i1,j]M[i,j]=M[i-1,j] if 0<j<ai,0< j< a_i,

M[i,j]=1M[i,j]=1 if j=ai,j=a_i, and

M[i,j]=max{M[i1,j],M[i1,jai]}M[i,j]=\max\{M[i-1,j],M[i-1,j-a_i]\} if 17>j>ai.17> j>a_i.

The last equality is determined by the following idea. If M[i1,j]=1,M[i-1,j]=1, then jj can be formed as a sum of a subset of {a0,...,ai}\{a_0,...,a_i\} that does not include ai.a_i. If M[i1,jai]=1,M[i-1,j-a_i]=1, then jj can be formed as a sum of a subset of {a0,...,ai}\{a_0,...,a_i\} that does include ai.a_i. If M[i1,j]=M[i1,jai]=0,M[i-1,j]=M[i-1,j-a_i]=0, then there is no way to form jj as a sum of a subset of {a0,...,ai}.\{a_0,...,a_i\}.

Following the rules above, we give a complete characterization of MM as follows:

(ai,j)(a_i,j)0011223344556677889910101111121213131414151516161717
55110000000011000000000000000000000000
88110000000011000011000000001100000000
22110011000011001111001100001100110000
44110011001111111111111111111111110011
66110011001111111111111111111111111111

Since M[4,17]=1M[4,17]=1, we see that 1717 can be formed as a sum of a subset of SS. Futhermore, the chart above can used to see that 17=4+8+517 = 4 + 8 + 5.