3

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.

Improve this question
8
  • I don't quite follow why you need a two dimensional list... Commented Jan 10, 2017 at 13:47
  • @WillemVanOnsem Isn't that the dynamic programming approach for this problem? 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. Commented Jan 10, 2017 at 13:49
  • can you reuse a coin, or can every number be only used once? 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 Commented Jan 10, 2017 at 13:51

1 Answer 1

Reset to default
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.

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

7 Comments

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?
@Stupid.Fat.Cat: actually it is, one simply needs to modify the code a bit.
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
@Stupid.Fat.Cat: keep in mind this only works for positive values.
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.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.