Responsive image

问题 1535 --还是01背包

1535: 还是01背包

时间限制: 10 Sec  内存限制: 128 MB
提交: 3  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

有n个重量和价值分别为 wi 和 vi 的物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

输入描述

多组测试数据。
每组测试数据第一行输入n 和 W ，接下来有n行，每行输入两个数，代表第i个物品的wi 和 vi。
1 <= n <=40
1 <= wi <= 10^15
1 <= vi <= 10^15
1 <= W <= 10^15

输出描述

每组数据输出一行，代表挑选方案中价值总和的最大值。

样例输入

4 5
2 3
1 2
3 4
2 2

样例输出

7

提示

超大背包题

来源

陆熠十四 

[提交][状态]
ACM算法攻关部