2063 - 武林外传第七十一回续
吕秀才流连吉庆街，金湘玉巧设惊魂计
秀才去十八里铺收帐，迟迟不归，小郭心急，派人去打探。小六回来之后，道出了一个天大的秘密，秀才竟然流连青楼，与老板娘眉来眼去，玩得正欢。召开了紧急会议之后，众人轮流过去收拾秀才，却一个都没有回来，老白，大嘴，甚至是小六，都被充满魅力的老板娘留在了十八里铺……
原来次青楼非彼青楼，只是名字叫青楼的酒楼。别人不回来没关系，可是老白都乐不思蜀的死样，佟湘玉恨的牙痒痒。待青楼老板娘金湘玉登门拜访的时候，佟掌柜心里暗想：好一个金湘玉，虽然长得没我漂亮。。。可是。。。竟然比我要瘦！！！事事争先的佟掌柜怎么能容忍奇耻大辱！！！好吧。。。说是迟那时快，佟掌柜制定了一份严格的减肥计划。具体细节由秀才写出：
首先，每天根据早晨测量的新陈代谢值计算出这一天所需的最低热量m （0<=m<=10000）。
其次，再由大嘴提供纯天然无污染高纤维低脂肪的减肥食品若干n(0< n< =10)。佟掌柜按口味挑选其中若干种食品。
但是两会下达一号文件：浪费可耻！！！所选食物必须全部吃完！！！
看起来万无一失的减肥方案让佟掌柜暂时心安，可是经过一天问题马上就来了。原来佟湘玉并不知道每份食物的热量，吃来吃去又挨饿又没有瘦。现在佟掌柜高薪聘请你帮助她计算在不超过每天的最小热量摄取值得情况下，怎样吃的最多？？
Input
输入包含多组测试数据，每组数据第一行包含两个正整数m和n，分别代表每天规定的热量摄入值和大嘴提供的食物数量，接下来n行每行由两个正整数组成，代表该食物的热量和重量。输入以m，n为0时结束。
Output
输出减肥中的佟掌柜每天最多能吃多重的食物。格式参照示例。
Examples
Input
2000 9 135 200 135 70 100 470 60 70 120 50 240 40 240 60 100 110 100 75 0 0
Output
The most weight is 1145g.
Hint
佟掌柜从n种食物中挑选若干种，所选择的每一份食物必须全部吃完，即获得该食物的全部热量。
Solution C++
#include <bits/stdc++.h> using namespace std; int m, n; int f[100009]; int main() { while (cin >> m >> n) { if (m == 0 && n == 0) break; for (int i = 1; i <= n; i ++) { int c, w; cin >> c >> w; for (int j = m; j >= c; j --) { f[j] = max(f[j], f[j - c] + w); } } printf("The most weight is %dg.\n", f[m]); } return 0; }
Hint
佟掌柜从n种食物中挑选若干种，所选择的每一份食物必须全部吃完，即获得该食物的全部热量。