python - 无法在python中实现动态规划表算法

Question

我在用 python 创建表时遇到问题。基本上我想为每个数字建立一个表，告诉我是否可以使用它来分解另一个(它是来自 Can brute force algorithms scale? 中接受的答案的表算法)。这是伪代码:

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

这是我的 python 实现:

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]

所以我期望的是，如果 target_result 设置为 8，它会显示列表 data 中的每个项目如何用于分解该数字。对于所有工作的 8、1、2、4，所以我希望它们都是真实的，但这个程序使一切都真实。例如，1 应该只能被 1(而不是 2 或 4)分解，但是当我将它作为 1 运行时，我得到:

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

任何人都可以帮我理解代码有什么问题吗？或者我可能不理解我所指的答案中发布的算法。

(注意:我可能完全错了，但我知道 defaultdict 会创建条目，即使它不存在，如果条目存在，算法会将其变为真，也许这就是我不确定的问题，但它是我试图走的思路，但它对我不起作用，因为它似乎破坏了整体实现) 谢谢!

Answer 1

如果您使用 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