登录/注册
221. 01背包问题之 2(挑战程序设计竞赛)
时间限制: C/C++ 1000 ms | 其他语言 2000 ms
内存限制: C/C++ 64 MB | 其他语言 128 MB
尝试次数: 278 | 通过次数: 110
尝试人数: 60 | 通过人数: 51
标签: 动态规划,背包
难度: 中等
0
3

nn 个重量和价值分别为 wiw_i,viv_i 的物品。从这些物品中挑选出总重量不超过 WW 的物品,求所有挑选方案中价值总和的最大值.

输入

  • 输入数据第一行有两个整数 nnWW,接下来会有 nn 行,分别表示 nn 个物品的对应的 wiw_iviv_i
  • 1n1001 \leq n \leq 100
  • 1wi1071 \leq w_i \leq 10^7
  • 1vi1001 \leq v_i \leq 100
  • 1W1091 \leq W \leq 10^9

输出

  • 输出一个整数, 表示题目要求的最大价值
样例 1
输入
4 5
2 3
1 2
3 4
2 2
输出
7