knapSack的问题是返回一个值的列表，而不是总的值。

Question

def knapSack(W, wt, val, n):

    if n == 0 or W == 0:
        return 0

    if (wt[n - 1] > W):
        return knapSack(W, wt, val, n - 1)

    else:
        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
                   knapSack(W, wt, val, n - 1))

到目前为止，我有这段代码作为参考.我是否可以返回一个值的列表，而不是返回一个总的值？

谢谢你

Answer 1

分析这段代码，我认为你的参数是。W--背包的最大重量, wt--物品重量列表, val--物品值列表, n--物品数量. 我提出了一个不同的方法，完全不使用递归，利用的是 powerset 从 迭代工具 而不是。

from itertools import combinations, chain

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def weight(subset): # returns total weight of items in subset
    return sum(i[0] for i in subset)

def value(items): # returns total value of items in subset
    return sum(i[1] for i in subset)

def knapsack(W, items): 
    return max( (subset for subset in powerset(items) if weight(subset) <= W), key=value)

val = [60, 100, 120]
wt = [10, 20, 30]
W = 50

print(knapsack(W, zip(wt, val)))

# prints ((20, 100), (30, 120)) ie. pairs (weight, value) of the best combination