有 n 件物品,每件物品都有重量和价值。
第 i 件物品的重量为 w_i,价值为 v_i。
现在有一个容量为 W 的背包。
每件物品只能选择一次,也可以不选择。
要求在所有选中物品的重量总和不超过 W 的前提下,使物品的价值总和最大。
请输出能够获得的最大价值。
第一行输入两个正整数 n,W,分别表示物品数量和背包容量。
接下来 n 行,每行输入两个正整数 w_i,v_i,分别表示第 i 件物品的重量和价值。
输出一个整数,表示能够获得的最大价值。
4 7 2 3 3 4 4 5 5 8
11
选择第 1 件和第 4 件物品:
满足容量限制,且总价值最大。
因此答案为 11。