CODEWITHSUNDEEP
pythondynamic-programming
Stupid.Fat.Cat
Stupid.Fat.Cat

Reputation: 11295

Finding subset sum using dynamic programming

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.

Upvotes: 3

Views: 1589

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

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.

Upvotes: 4

Related Questions