动态规划系列之八多重背包问题

问题

法外狂徒张三是一个探险家，有一次巧合之下进入到一个有宝藏的洞穴里。这个洞穴有很多个重复的宝贝，每个宝贝的重量不一样。具体来说有：
A 重 2 价值为 2 数量2
B 重 3 价值为 6 数量2
C 重 4 价值为 4 数量3
D 重 4 价值为 5 数量1
E 重 1 价值为 3 数量1
现在张三就只有一个背包，这个背包承重为10，张三想知道如何装才能带走价值最大的宝藏？

思路

以上问题的描述就是多重背包问题，和01背包不同的地方就在于每一个宝贝的数量不是一个，不是无数个，而是有限定的数量。那么在01背包的问题上解决多重背包的问题。分析两个不同之处：
01背包：宝贝只有一个
多重背包：宝贝有多个
多重背包问题和01背包问题是十分相似的，所以完全可以用01背包的思想来解决这个问题。回忆一下01背包问题的思路，01背包的大体思路可以总结为：
在拿第n个宝贝时，已经知道了前n-1个宝贝放入背包中的最优解，所以放入第n个宝贝时，就是和前n-1个最优解比较，如果第n个比前n-1个最优解还好，那就放入，否则就不放入
多重背包和01背包在宝贝的种类上是一样的，只是每一种宝贝的数量不同。拿某一件物品时，01背包只拿一个，而多重背包可以拿多个。解决多重背包问题就每取一个宝贝是就把这个种类的宝贝全部取完。具体来说在循环时增加一个数量的循环就可以了。

代码

weight = [0,2,3,4,4,1]
value = [0,2,6,4,5,3]
k = [0,2,2,3,1,1]
weight_most=10


bag = [0 for i in range(weight_most+1)]
for i in range(1,len(weight)):
    # 和01背包不同的，多重背包里多个物品都要放入背包中
    for _ in range(k[i]):
        for j in range(weight_most,0,-1):
            if j >= weight[i]:
                bag[j] = max(bag[j-weight[i]]+value[i],bag[j])
        print(bag)
        
print(bag[-1])