1281: 赫尔曼斯的礼物1（背包问题）

[命题人 : 2211247]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交解决: 8提交量: 15统计

题目描述  复制

（故事背景，与题目无关）
阿列克辛·赫尔曼斯可谓是一个“落魄的贵族”了——他已经年过四十，却从来没经历过一段真正的爱情。偶然间，他在时尚杂志《Hydrogen》上了解到了米塞莉娜·诺塔斯，并对她的美貌一见倾心。他找了一个精致的盒子，打算送米塞莉娜一些礼物，博取她的芳心。赫尔曼斯心想：“米塞莉娜一定喜欢珍贵的珠宝。可惜这盒子太小了，我要尽可能装下价值更高的东西。”（故事的后续？详见1282）
（正题）
请编写Python程序，告诉赫尔曼斯在容量有限的盒子里面怎样装下更高价值的东西。

输入

第一行：一个整数，盒子的体积
第二行：一个整数n
接下来n行：各个物品的名称、体积、价值，用空格分隔，后两项均为正整数

输出

第一行：各种礼物的名称，用空格分隔
第二行：这个盒子里能装下的最大价值

样例输入  复制 

4
3
钻石 1 2500
红宝石 3 5400
蓝宝石 4 5900

样例输出  复制 

钻石 红宝石
7900

提示

如果有多种结果价值相同，输出最先找到的结果。
例如：
2
4
A 1 100
B 2 198
C 1 100
D 1 100
输出：
A C
200
 
再例如：
2
4
A 1 100
B 2 200
C 1 100
D 1 100
输出：
B
200

再例如：
2
6
A 1 100
B 2 200
C 1 100
D 1 100
E 1 101
F 1 100
输出：
A E
201

必须/禁用关键字

无

来源/分类

动态规划 
提交