Problem1723--完全背包

1723: 完全背包

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 3Submit: 3Statistics

Description

一个旅行者有一个最多能装M公斤的背包，现在有n种物品，每件物品数量无限的，它们的重量分别是wi，它们的价值分别是vi元。从中选取若干件（同一物品可以选任意件），求旅行者能获得最大总价值。

Input

第1行：两个整数，M背包容量（M<=1000）和n物品数量（n<=30）；
第2至n+1行：每行两个整数wi,vi,表示每个物品的重量和价值。

Output

一个数，表示最大总价值。

Sample Input Copy 

10 4
2 1
3 3
4 5
7 9

Sample Output Copy 

12

Source/Category

动态规划 完全背包 
SubmitWeb Board