#P3048. 奥奥购物
奥奥购物
Description
当前有N件物品和一个容积为V的背包。已知第i
件物品的体积是ci
,价值是wi
。每种物品有且仅有一件,并且体积不可分割。现在你需要选出若干件物品,在它们的重量之和不超过V
的条件下,使得价值总和尽可能大。
Input Format
输入 n+1 行
第一行输入两个整数 VN,分别表示背包容积以及物品数量。
第 2~n+1 行,每行输入两个变量,分别是表示物品的价值和体积。
Output Format
输出一行,表示N件物品中,在背包容积V内能够挑选的物品的最大价值。
10 5
2 1
3 5
2 5
3 4
4 3
15