Проблемы с заметками и извлечением решений в задаче о том, что я делаю не так? ⇐ Python

[Anonymous]

Введение: < /p>
Проблема с точкой цели, которую я пытаюсь решить, - это проблема динамического программирования, в которой мне предоставлен список натуральных чисел и целевого числа (TGT). Программа состоит в том, чтобы использовать числа в списке, чтобы подвести итоги целевого номера или приблизиться как можно ближе. В целом есть две половины моего кода, первая функция-TargetSum, а вторая getBestTargetSum. Как он называет Targetsum, а также записывает решения в таблицу D. Это, я думаю, это то, где мои проблемы лежат. В другой версии этого кода у меня появились отрицательные значения в D, что, вероятно, указывает на то, что, возможно, такие индексы, как (0,0), были потеряны для пустоты из -за того, что я пытался избавиться от негативных значений из таблицы ... < /p>
, во -вторых, результат этих кодов возвращает точно противоположное из -за того, что он должен делать. При предоставлении списка чисел, т.е. {1, 2, 3, 4, 5, 10} и a tgt = 15, вместо выбора {5, 10} для разницы 0, он выбирает и возвращает {1, 2, 5} вместо этого. < /P>
Вот мой код, прощайте меня за беспорядок. Я всего лишь ноду. Спасибо за помощь. < /P>

def targetSum(S, i, tgt):
k = len(S)

if tgt < 0:
return float('inf')

if i == k and tgt >= 0:
return tgt

else:
return min(targetSum(S, i+1, tgt-S), targetSum(S, i+1, tgt))

def getBestTargetSum(S, tgt):

k = len(S)
D = {} # Solutions table
T = {} # Memo table

# Case 1: At the end
for j in range(tgt+1):
T[(k,j)] = j
#D[(k,j)] = k,j

for i in range(k-1, -1, -1):
for j in range(tgt+1):
# Case 2: Skip
if j < 0:
T[(i,j)] = float('inf')
D[(i,j)] = i+1,j

# Case 3: Choice
else:
include = targetSum(S, i+1, tgt-S)
exclude = targetSum(S, i+1, tgt)

if include = 0:
D[(i,j)] = (i+1, j - S)

else:
T[(i,j)] = exclude
D[(i,j)] = (i+1, j)

# Retrieving solution from D
res = []

key = 0,15

while key in D:

value = D[key]

if value[1] != key[1]:
i = key[0]
res.append(S)

key = value
print(i,j,':',res)

return res


Подробнее здесь: https://stackoverflow.com/questions/794 ... lem-what-a