У меня проблемы с созданием таблицы в python.По сути, я хочу построить таблицу, в которой для каждого числа будет указано, смогу ли я использовать ее для разбиения другого (это таблица, взятая из принятого ответа в Могут ли алгоритмы грубой силы масштабироваться? ).Вот псевдокод:
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, он показывает, как каждый элемент вlist data может использоваться для разбивки этого числа.Для 8, 1,2,4 для всей работы, поэтому я ожидаю, что все они будут правдой, но эта программа делает все правдой.Например, 1 можно разбить только на 1 (а не на 2 или 4), но когда я запускаю его как 1, я получаю:
(1, 2) : True
(1, 0) : False
(1, 3) : True
(1, 1) : True
Может кто-нибудь помочь мне понять, что не так скод?или, возможно, я не понимаю алгоритм, который был опубликован в ответе, на который я ссылаюсь.
(Примечание: я могу быть совершенно неправ, но я узнал, что defaultdict создает записи, даже если их нет, и если записьсуществует, алгоритм превращает его в истину, может быть, в этом и проблема, я не уверен, но это была мысль, которую я пытался использовать, но она не сработала для меня, потому что, кажется, нарушает общую реализацию) Спасибо!