1179: 部分背包问题
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:59
Solved:30
Description
给定一个能装最大重量为 M 的背包和 N 种食品,这 N 种食品如食盐,白糖,大米等可以部分取过来想取多少就取多少。
已知第 i 种食品的最多拥有 Wi 公斤,其商品价值为 Vi 元/公斤,编程确定一个装货方案,使得装入背包中的所有物品总价值最大。
Input
第一行两数 N 和 M ,分别表示食品种类和背包容量。
接下来N行,每行两个数 Wi 和 Vi ,分别表示第i种食品的最多拥有重量和价值。
Output
一行一个数表示最大价值。
Sample Input Copy
3 5
4 2
3 6
5 3
Sample Output Copy
24
HINT
1≤N,M,Wi,Vi≤104