0/1背包[1]

测试数据来自 system/1008

作业已超过截止时间,您无法递交本题目。

时间限制:1秒  内存限制:256M


【问题描述】

  有 nn 个物品,物品 ii 的体积为 viv_i,价值为pip_i。现在要选一些物品装入容量为 CC 的背包(每个物品要么选,要么不选,不能只装一部分),使得背包中物品的价值和最大。

【输入格式】

  第 11 行是整数 nnCC,表示有 nn 个物品,背包的容量为 CC
  接下来的 nn 行,每行两个整数:viv_ipip_i,表示物品 ii 的体积和价值。

【输出格式】

  一个整数,表示能得到的最大价值。

【输入输出样例】

 Input

5 100
77 92
12 12
29 87
50 46
99 90

 Output

145

【数据限制】

 1n5001 ≤ n ≤ 500
 1vi,C1051 ≤ v_i,C ≤ 10^5
 1pi1061 ≤ p_i ≤ 10^6

【来源】

  Mr.he

动态规划之最优子集练习题

未认领
状态
已结束
题目
10
开始时间
2025-02-13 00:00
截止时间
2025-03-31 23:59
可延期
24.0 小时