我们需要返回项目的最大值，以及构成该最大值的项目。
列表输入格式为[[weight1, value1], [weight2, value2]]。
使用下面的代码，我只返回最大值。
有人可以帮我把那个值(value)连同元素一起退回吗？
def knapsack(capacity, itemList):
"""
Returns the maximum value and the list of items to keep.
"""
if len(itemList) == 0:
return 0
elif itemList[-1][0] > capacity:
return knapsack(capacity, itemList[:-1])
else:
return max(
knapsack(capacity, itemList[:-1]),
knapsack(capacity-itemList[-1][0], itemList[:-1]) + itemList[-1][1])
print (knapsack(6, [[1, 4], [5, 150], [4, 180]]))
# should return [184, [[1, 4], [4, 180]]]
# returns 184
请您参考如下方法:
我会通过存储递归子调用的解决方案来做到这一点。您的解决方案基本上是说 N 件背包问题的解决方案，容量 C 是以下项的最大值:
Soln(N,C) = max ( Soln(N-1,C), Soln(N-1, C-W_n) + Vc)
因此，如果我们将这些子问题的解决方案存储在字典中(也可以使用数组)，您可以使用相同的逻辑向后工作。看N,C问题的解是否等于N-1,C问题。如果是，则元素 N 不在袋子里，否则它在袋子里。
d = {} #maps from (itemCount, capacity) to best Value
# (also useful for when/if you convert to dp/memoized version)
def knapsack(capacity, itemList):
"""
Returns the maximum value and the list of items to keep.
"""
if len(itemList) == 0:
return 0
elif itemList[-1][0] > capacity:
ans = knapsack(capacity, itemList[:-1])
d[(len(itemList), capacity)] = ans
return ans
else:
ans = max(knapsack(capacity, itemList[:-1]), knapsack(capacity-itemList[-1][0], itemList[:-1]) + itemList[-1][1])
d[(len(itemList), capacity)] = ans
return ans
items = [[5, 150], [1, 4], [4, 180]]
startCap = 6
print knapsack(startCap, items)
#Work Backwards
itemNo = 3
startCap = 6
curValue = d[(itemNo,startCap)]
myList = []
while itemNo > 0:
if (itemNo == 1 or curValue != d[(itemNo-1, startCap)]) and items[itemNo-1][0] < startCap: #item was included
myList = [itemNo] + myList
startCap -= items[itemNo-1][0] #subtract the capacity
curValue -= items[itemNo-1][1]
itemNo -= 1
print myList #outputs [2,3]
