完全背包问题

Time Limit: 1s Memory Limit: 256MB Submissions: 329 Solved: 195 
Description
一个旅行者有最多能装M公斤的背包,现有N件物品,它们的重量分别为W1,W2,W3,...Wn,它们的价值分别为C1,C2,C3...Cn。注意:物品的数量是无限的。求旅行者应选哪几种物品装入背包(同一种物品可以多次选取),使包内物品的总价值最大。
Input
第一行:两个整数,m(背包容量,m《=200)和n(物品数量,n《=30)
第2行。。。n+1行:每行两个整数wi和ci,表示每个物品的重量和价值
Output
仅一行,一个数,表示最大总价值
Sample Input
12 4
2  1
3  3
4  5
7  9

Sample Output
max=15