问题描述
我有在Python中创建一个表的问题。基本上我想建立一个表，对于每一个数字告诉我，如果我可以用它来从的）。这里的伪code：
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
下面是Python实现，我有：
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]
因此，如果 target_result 设置为8我所期望的是，它显示了如何在列表中每个项目数据即可被用来打破这个数字下降。对于8，1,2,4的所有工作，所以我希望他们全部是真实的，但这个方案是使一切真实。例如，1只应能由1（而不是2或4），但是当我运行它作为1，我得到细分：
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
谁能帮助我了解什么是错的code？或许我不理解被张贴在回答我指的是该算法。
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.
（注：我可能是完全错误的，但我了解到，defaultdict创建条目，即使它不存在，如果存在条目的算法中打开它，以真正的，也许这就是我不知道这个问题，但它是思想路线我试图去，但它并没有为我工作，因为它似乎打破了整体的FPGA实现）谢谢！
(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!
推荐答案
在code工作，如果你使用的是 RecursivelyListAllThatWork（） ：
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)
输出
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
这篇关于无法实现的Python动态规划表算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！