Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Views: 187
Image: ubuntu2004
Kernel: Python 3 (system-wide)

The Sum Finder Problem

A 2D2D array m[i][j]m[ i ][ j ] is created with i=(length of set)i=(length\ of\ set) multiplied by j=(size of the target value)j=(size\ of\ the\ target\ value).

If there exists a subset of elements in m[i]m[ i ] from i=0 to ii = 0\ to\ i, whose sum is equal to the value of m[j]m[ j ];

m[i][j]=1m[ i ][ j ] =1.

Else, m[i][j]=0m[ i ][ j ] = 0.

If the value in the m[i1][j]m[ i-1 ][ j ] row is 11, we can immediately evaluate the m[0 to i][j]m[0\ to\ i ][ j ] row to 11 without any extraneous calculations, since we already know a subset of values equal to the value of m[i][j]m[ i ][ j ] exists.

Target value = 1717
Set = [5,8,2,4,6][5, 8, 2, 4, 6]

For the first row ii, we only have one value in our subset; [5][5].

So only the array element holding the value of j=[5]j=[5] will be appended to 11. The rest are 00.

For the second row, ii, we have two values in our subset; [5,8][5, 8].

So the array element holding the values of j=[8,5+8=13]j=[8, 5+8=13] will be appended to 11. The rest are 00.

Since we have already evaluated the elements in the m[i1][j]m[i-1][j] position, we no longer need to evaluate the previous row and column numbers for values which have already been appended to 11 but rather can continue to place a 11 in all the remaining m[0 to i][j]m[0\ to\ i][j] positions. We only need to evaluate the new additions to our subset.

For the third row, ii, we have three values in our subset; [5,8,2][5, 8, 2].

j=[5,8,13]j=[5, 8, 13] have already been evaluated. So, we only need to evaluate the addition of 22 to the subset. The array elements holding the values of j=[2,5+2=7,8+2=10,5+8+2=15]j=[2, 5+2=7, 8+2=10, 5+8+2=15] need to be appended to 11. The rest are 00.

For the fourth row, ii, we have four values in our subset; [5,8,2,4][5, 8, 2, 4].

j=[2,5,7,8,10,13,15]j=[2, 5, 7, 8, 10, 13, 15] have already been evaluate. So, we only need to evaluate the addition of 44 to the subset. The array elements holding the values of j=[4,4+2=6,4+5=9,4+2+5=11,4+8=12,4+2+8=144+8+5=17]j=[4, 4+2=6, 4+5=9, 4+2+5=11, 4+8=12, 4+2+8=14 4+8+5=17] need to be appended to 11. The rest are 00.

Furthermore, we have already evaluated the element holding the value of j=[2,5,7,8,10,13]j=[2, 5, 7, 8, 10, 13] to be 11, so the additional sum of 44 to any of these values in our subset will append the values in the positions of the values j=[2+4,5+4,7+4,8+4,10+4,13+4]j=[2+4, 5+4, 7+4, 8+4, 10+4, 13+4] to all be 11.

We already have our target value of 1717. But for the sake of this exercise, lets evaluate the final row.

For the fifth row, ii, we have all five values in our subset; [5,8,2,4,6.][5, 8, 2, 4, 6.].

All other values in jj have been appended to 11 with the exception of the values of j=[1,3,16]j=[1, 3, 16]. We have already evaluated the value of j=[10]j=[10] to be 11, so the addition of 6 will guarantee that some combination of the subset will equal a sum of 1616, so we appended it to 11. The others remain 00.

Target value =1818
Set = [5,7,3,4,6][5, 7, 3, 4, 6]

For the first row ii, we only have one value in our subset; [5][5].

So only the array element holding the value of j=5j={5} will be appended to 11. The rest are 00.

For the second row, ii, we have two values in our subset; [5,7][5, 7].

So the array element holding the values of j=[7,5+7=12]j=[7, 5+7=12] will be appended to 11. The rest are 00.

For the third row, ii, we have three values in our subset; [5,7,3][5, 7, 3].

j=[5,7,12]j=[5, 7, 12] have already been evaluated. So, we only need to evaluate the addition of 33 to the subset. The array elements holding the values of j=[3,5+3=8,7+3=10,5+7+3=15]j=[3, 5+3=8, 7+3=10, 5+7+3=15] need to be appended to 11. The rest are 00.

For the fourth row, ii, we have four values in our subset; [5,7,3,4][5, 7, 3, 4].

j=[3,5,7,8,10,12,15]j=[3, 5, 7, 8, 10, 12, 15] have already been evaluate. So, we only need to evaluate the addition of 44 to the subset. The array elements holding the values of j=[4,4+5=9,7+4=11,7+3+4=14,3+4+5+7=16]j=[4, 4+5=9, 7+4=11, 7+3+4= 14, 3+4+5+7=16] need to be appended to 11. The rest are 00.

Furthermore, we have already evaluated the element holding the value of j=[5,7,10,12]j=[5, 7, 10 , 12] to be 11, so the additional sum of 44 to any of these values in our subset will append the values in the positions of the values j=[5+4,7+4,10+4,12+4]j=[5+4, 7+4, 10+4, 12+4] to all be 11.

For the fifth row, ii, we have all five values in our subset; [5,7,3,4,6][5, 7, 3, 4, 6].

All other values in jj have been appended to 11 with the exception of the values of j=[1,2,6,13,17,18]j=[1, 2, 6, 13, 17, 18]. We have already evaluated the value of j=[7,11,12]j=[7, 11, 12] to be 11, so the addition of 66 will guarantee that some combination of the subset will equal a sum of j=[6,13,17,18]j=[6, 13, 17, 18] so we appended them to 11. The others remain 00.