算法题 背包问题-多重背包（Python）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法题 背包问题-多重背包（Python），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含733字，纯文字阅读大概需要2分钟。

内容图文

题目

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数 N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

 

0<N,V≤100
0<vi,wi,si≤100

提示：

本题考查多重背包的二进制优化方法。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

代码

 

N, V = map(int, input().split())
dp = [0] * (V+1)

# 算法复杂度o(N*S*V)
for _ in range(N):
    v, w, s = map(int, input().split())
    for _ in range(s):
        for j in range(V, v-1, -1):
            dp[j] = max(dp[j], dp[j - v] + w)
print(dp[-1])
    

 

内容总结

以上是互联网集市为您收集整理的算法题 背包问题-多重背包（Python）全部内容，希望文章能够帮你解决算法题 背包问题-多重背包（Python）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---