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,表示每个物品的重量和价值

输出

仅一行,一个数,表示最大总价值

样例输入 复制

12 4
2  1
3  3
4  5
7  9

样例输出 复制

max=15