Unable to implement a dynamic programming table algorithm in python

Question

I am having problems creating a table in python. Basically I want to build a table that for every number tells me if I can use it to break down another(its the table algo from the accepted answer in Can brute force algorithms scale?). Here's the pseudo code:

for i = 1 to k
    for z = 0 to sum:
        for c = 1 to z / x_i:
            if T[z - c * x_i][i - 1] is true:
                set T[z][i] to true

Here's the python implementation I have:

from collections import defaultdict


data = [1, 2, 4]
target_sum = 10

# T[x, i] is True if 'x' can be solved
# by a linear combination of data[:i+1]
T = defaultdict(bool)           # all values are False by default
T[0, 0] = True                # base case


for i, x in enumerate(data):    # i is index, x is data[i]
    for s in range(target_sum + 1): #set the range of one higher than sum to include sum itself
        for c in range(s / x + 1):  
            if T[s - c * x, i]:
                T[s, i+1] = True

#query area   
target_result = 1
for node in T:
    if node[0]==target_result:
        print node, ':', T[node]

So what I expect is if target_result is set to 8, it shows how each item in list data can be used to break that number down. For 8, 1,2,4 for all work so I expect them all to be true, but this program is making everything true. For example, 1 should only be able to be broken down by 1(and not 2 or 4) but when I run it as 1, I get:

(1, 2) : True
(1, 0) : False
(1, 3) : True
(1, 1) : True

can anyone help me understand what's wrong with the code? or perhaps I am not understanding the algorithm that was posted in answer I am referring to.

(Note: I could be completely wrong, but I learned that defaultdict creates entries even if its not there, and if the entry exists the algo turns it to true, maybe thats the problem I'm not sure, but it was the line of thought I tried to go but it didn't work for me because it seems to break the overall implemention) Thanks!

Answer 1

The code works if you print the solution using RecursivelyListAllThatWork():

coeff = [0]*len(data)
def RecursivelyListAllThatWork(k, sum): # Using last k variables, make sum
    # /* Base case: If we've assigned all the variables correctly, list this
    # * solution.
    # */
    if k == 0:
        # print what we have so far
        print(' + '.join("%2s*%s" % t for t in zip(coeff, data)))
        return
    x_k = data[k-1]
    # /* Recursive step: Try all coefficients, but only if they work. */
    for c in range(sum // x_k + 1):
       if T[sum - c * x_k, k - 1]:
           # mark the coefficient of x_k to be c
           coeff[k-1] = c
           RecursivelyListAllThatWork(k - 1, sum - c * x_k)
           # unmark the coefficient of x_k
           coeff[k-1] = 0

RecursivelyListAllThatWork(len(data), target_sum)

Output

10*1 +  0*2 +  0*4
 8*1 +  1*2 +  0*4
 6*1 +  2*2 +  0*4
 4*1 +  3*2 +  0*4
 2*1 +  4*2 +  0*4
 0*1 +  5*2 +  0*4
 6*1 +  0*2 +  1*4
 4*1 +  1*2 +  1*4
 2*1 +  2*2 +  1*4
 0*1 +  3*2 +  1*4
 2*1 +  0*2 +  2*4
 0*1 +  1*2 +  2*4

Answer 2

As a side note, you don't really need a defaultdict with what you're doing, you can use a normal dict + .get():

data = [1, 2, 4]
target_sum = 10

T = {}
T[0, 0] = True

for i,x in enumerate(data):
    for s in range(target_sum + 1):    # xrange on python-2.x
        for c in range(s // x + 1):
            if T.get((s - c * x, i)):
                T[s, i+1] = True

If you're using J.S. solution, don't forget to change:

if T[sum - c * x_k, k - 1]:

with:

if T.get((sum - c * x_k, k - 1)):

Answer 3

Your code is right.

1 = 1 * 1 + 0 * 2, so T[1, 2] is True.

1 = 1 * 1 + 0 * 2 + 0 * 4, so T[1, 3] is True.

As requested in the comments, a short explanation of the algo: It calculates all numbers from 0 to targetsum that can be represented as a sum of (non-negative) multiples of some of the numbers in data. If T[s, i] is True, then s can be represented in this way using only the first i elements of data.

At the start, 0 can be represented as the empty sum, thus T[0, 0] is True. (This step may seem a little technical.) Let x be the 'i+1'-th element of data. Then, the algorithm tries for each number s if it can be represented by the sum of some multiple of x and a number for which a representation exists that uses only the first i elements of data (the existence of such a number means T[s - c * x, i] is True for some c). If so, s can be represented using only the first i+1 elements of data.