3068: 0-1 背包 书本例题P498
[Creator : ]
Description
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 C i ，得到的价值是 W i 。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。
Input
第 1 行两个正整数，分别表示 N 和 V，中间用一个空格隔开。
第 2 行 N 个正整数，表示 C i ，中间用一个空格隔开。
第 3 行 N 个正整数，表示 W i ，中间用一个空格隔开。
其中：1≤N≤100，1≤V≤10^6 ，1≤C i ≤10000，1≤W i ≤10000。
第 2 行 N 个正整数，表示 C i ，中间用一个空格隔开。
第 3 行 N 个正整数，表示 W i ，中间用一个空格隔开。
其中：1≤N≤100，1≤V≤10^6 ，1≤C i ≤10000，1≤W i ≤10000。
Output
一行一个正整数，表示最大的价值总和。
Sample Input Copy
4 20
8 9 5 2
5 6 7 3
Sample Output Copy
16