3011 - 0-1背包问题-2
时间限制 : 1 秒
内存限制 : 16 MB
有N件物品和一个容量为C的背包。放入第i件物品耗费的空间是w_i，得到的价值是v_i。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。
输入
第1行两个正整数，分别表示N和C，中间用一个空格隔开。
第2行N个正整数，表示w_i，中间用一个空格隔开。
第3行N个正整数，表示v_i，中间用一个空格隔开。
其中：1≤N≤1000，1≤C≤10^6 ，1≤w_i≤10000，1≤v_i≤10000。
输出
一行一个正整数，表示最大的价值总和。
样例
输入
4 20 8 9 5 2 5 6 7 3
输出
16
提示
本题与0-1背包（2010）题面完全一致，唯一的区别为N的取值范围和内存约束。
来源
动规专题