Finding subset sum using dynamic programming

Question

I'm practicing Dynamic Programming and I'm struggling with debugging my code. The idea is to find if a sum is possible given a list of numbers. Here's my code:

a = [2,3,7,8,10]
sum = 11
b = list(range(1, sum+1))
m = [[False for z in range(len(b))] for i in range(len(a))]

for i, x in enumerate(b):
    for j, y in enumerate(a):
        if x==y:
            m[j][i]=True
        elif y<x:
            m[j][i] = m[j-1][i]
        else:
            m[j][i] = m[j-1][i] or m[j-i][y-x]

for i, n in enumerate(m):
    print(a[i], n)

And here is the output:

2 [False, True, False, False, False, False, False, False, False, False, False]
3 [False, True, True, False, False, False, False, False, False, False, False]
7 [False, True, True, False, True, True, True, False, False, False, False]
8 [False, True, True, False, True, True, True, True, False, False, False]
10 [False, True, True, False, True, True, True, True, True, True, False]

As I understand it, in my else statement, the algorithm is supposed to go up 1 row and then look at the difference of x and y and check if that slot is possible. So for instance in the most obvious case, the last element in the last row. That would be 10(y)-11(x) which should go all the way back to index 1 on the row above it, which as we know it's True. Not entirely sure what I'm doing wrong, any help in understanding this would be greatly appreciated.

@WillemVanOnsem Isn't that the dynamic programming approach for this problem? — Stupid.Fat.Cat
– Stupid.Fat.Cat, Commented Jan 10, 2017 at 13:48
not per se. Do you know what you are doing here? If you simply want to know if you can use the coins to sum up to a given value, you can use a 1d list. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jan 10, 2017 at 13:49
can you reuse a coin, or can every number be only used once? — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jan 10, 2017 at 13:50
Yes @WillemVanOnsem I understand what I'm doing, the matrix on my paper makes sense. But the code isn't quite right. I could solve this using a greedy approach or the sorted left and right approach, but I"m trying to accomplish this through Dynamic Programming. It's not getting the answer that I'm interested in, moreso interested in solving this through DP — Stupid.Fat.Cat
– Stupid.Fat.Cat, Commented Jan 10, 2017 at 13:51

willeM_ Van Onsem · Accepted Answer · 2017-01-10 14:03:20Z

4

Given you only feed positive values, I don't quite follow why you need a two dimensional list. You can simply use a 1d list:

coins = [2,3,7,8,10]
sum = 11

Next we initialize the list possible that states whether it is possible to obtain a certain value. We set possible[0] to True since this sum can be accomplished with no coins.

possible = [False for _ in range(sum+1)]
possible[0] = True

Now you iterate over each coin, and over the list and "upgrade" the value if possible:

for coin in coins:
    for i in range(sum-coin,-1,-1):
        if possible[i]:
            possible[i+coin] = True

After that, the list possible shows for each value from 0 up to (and including sum) whether you can construct it. So if possible[sum] is True, the sum can be constructed.

For the given coins and sum, one gets:

>>> possible
[True, False, True, True, False, True, False, True, True, True, True, True]

So values 0, 2, 3, 5, 7, 8, 9, 10, 11 are constructible with the coins.

Edit: track the coins

You can also keep track of the coins by slightly modifying the code:

possible = [None for _ in range(sum+1)]
possible[0] = []
for coin in coins:
    for i in range(sum-coin,-1,-1):
        if possible[i] is not None:
            possible[i+coin] = possible[i]+[coin]

Now possible looks like:

>>> possible
[[], None, [2], [3], None, [2, 3], None, [7], [8], [2, 7], [10], [3, 8]]

So 0 can be constructed with coins [] (no coins); 2 can be constructed with [2] (one coin with value 2), 3 with [3], 5 with [2,3], etc.

edited Jan 10, 2017 at 14:03

answered Jan 10, 2017 at 13:55

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Stupid.Fat.Cat Over a year ago

Ah, ok I get this solution. But if I use a 1D array it's not possible to keep track of the coins used to reach to the solution, right?

willeM_ Van Onsem Over a year ago

@Stupid.Fat.Cat: actually it is, one simply needs to modify the code a bit.

Stupid.Fat.Cat Over a year ago

Ah, this is a much better solution than what the algorithm books are suggesting. Thank you! I'm still not entirely sure why my code didn't work but it's much more difficult to debug than a 1d array

willeM_ Van Onsem Over a year ago

@Stupid.Fat.Cat: keep in mind this only works for positive values.

Stupid.Fat.Cat Over a year ago

I suppose it is possible to normalize the negative values if I wanted to keep this solution and apply it for negative values as well. If I adjust the "largest" negative value to be 0 and increase the sum and every other element then it's possible to keep the solution.

|

Collectives™ on Stack Overflow

Finding subset sum using dynamic programming

1 Answer 1

Edit: track the coins

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Edit: track the coins

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related