1468 - 背包问题
时间限制 : 1 秒
内存限制 : 128 MB
有N件物品和一个容量为C的背包。放入第i件物品耗费的空间是w_i，得到的价值是v_i。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。
输入
第1行两个正整数，分别表示N和C，中间用一个空格隔开。
接着N行，每行2个数字，其中第i行的数字分别是 物品的价值v_i 、物品耗费的空间是w_i
输出
一行一个正整数，表示最大的价值总和。
样例
输入
4 20 5 8 6 9 7 5 3 2
输出
16
提示
1≤N≤30，1≤C≤ 10^9 ，1≤ w_i ≤10^9，1≤ v_i ≤10^9
来源
模板