问题
法外狂徒张三是一个探险家，有一次巧合之下进入到一个有宝藏的洞穴里。这个洞穴有很多个重复的宝贝，每个宝贝的重量不一样。具体来说有：
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])
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/196587.html
