问题 Y: 01背包问题(第五讲)

问题 Y: 01背包问题(第五讲)

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

题目描述

有容积为w的背包,有n个物品,并且已知每个物品的体积和价值,找到一种方法将若干物品放入背包,使背包中物品的总价值最大。输入物品件数n、背包容积w、每个物品的体积和价值,输出可以装入背包中的物品的最大总价值。n不大于15

输入

在第一行输入物品件数n和背包容积w,在下一行输入n个整数表示n个物品的体积,在第三行输入n个整数表示n个物品的价值。遇到文件末尾结束。

输出

在一行输出可以得到的背包中物品的最大总价值。

样例输入

4 8
2 4 4 3
3 4 3 6

样例输出

10

提示

[提交][状态]