CoCalc Public Filesprojects / Project 9 Solutions.ipynbOpen in with one click!
Author: Johann Thiel
Views : 69

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) 00 11 22 33 44 55 66 77 88 99 1010 1111 1212 1313 1414 1515 1616 1717
55 11 00 00 00 00 11 00 00 00 00 00 00 00 00 00 00 00 00
88 11 00 00 00 00 11 00 00 11 00 00 00 00 11 00 00 00 00
22 11 00 11 00 00 11 00 11 11 00 11 00 00 11 00 11 00 00
44 11 00 11 00 11 11 11 11 11 11 11 11 11 11 11 11 00 11
66 11 00 11 00 11 11 11 11 11 11 11 11 11 11 11 11 11 11

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.