1114: 完全背包问题
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：379
解决：229
题目描述
一个旅行者有最多能装M公斤的背包,现有N件物品,它们的重量分别为W1,W2,W3,...Wn,它们的价值分别为C1,C2,C3...Cn。注意：物品的数量是无限的。求旅行者应选哪几种物品装入背包（同一种物品可以多次选取），使包内物品的总价值最大。
输入
第一行：两个整数，m（背包容量，m《=200）和n（物品数量，n《=30）
第2行。。。n+1行：每行两个整数wi和ci，表示每个物品的重量和价值
第2行。。。n+1行：每行两个整数wi和ci，表示每个物品的重量和价值
输出
仅一行，一个数，表示最大总价值
样例输入 复制
12 4
2 1
3 3
4 5
7 9
样例输出 复制
max=15