python解决0-1背包问题
def knapSack(W, w, v):# W为背包容量
dp = [0] * (W + 1) #创建一个长度为 W + 1 的列表 dp
for i in range(1, len(w)):#第i件物品
for j in range(W, w[i] - 1, -1): #j是当前限重
dp[j] = max(dp[j], v[i] + dp[j - w[i]]) #求容量为j时的最大价值dp:加入第i件物品?还是不加
return dp[W]
a = knapSack(15, [0, 1, 1, 2, 4, 12], [0, 1, 2, 2, 10, 4])
print(a)