算法题 背包问题-分组背包 (Python）

内容导读

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

内容图文

题目

有 NN 组物品和一个容量是 VV 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vijvij，价值是 wij，其中 i 是组号，j 是组内编号。

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

输出最大价值。

输入格式

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

接下来有 N 组数据：

• 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
• 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式

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

数据范围

0<N,V≤100
0<Si≤100
0<vij,wij≤100

输入样例

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

输出样例：

8

代码 

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

for _ in range(N):
    s = int(input())
    vs, ws = [], []
    for _ in range(s):
        v, w = map(int, input().split())
        vs.append(v); ws.append(w)
    for j in range(V, 0, -1):
        for v, w in zip(vs, ws):
            if j >= v: dp[j] = max(dp[j], dp[j-v]+w)
print(dp[-1])

 

内容总结

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

内容备注

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

内容手机端

---