1634: 购物优惠
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:8
解决:7
题目描述
题目描述:
小惠听说超市正在打折促销,所以要制订一个得到最大优惠的购物计划。
小惠的体力可以提起 W 单位重量的东西,还有一个能装 V 个单位体积的购物袋,并详细的了解了各打折商品的重量、体积及此商品实际优惠的金额。她想在自己体力的限度和购物袋容积限度内,尽可能多地得到购物优惠。超市规定这些打折商品每种只能购买一件。
编程实现:
请你编写程序,制定一个购买商品的计划,求出小惠能得到的最大优惠金额和实际应购买的各商品序号。
输入描述:依次为 W、V 和 N(N 为商品种类数),所有数值均为不超过 100 的正整数
接下来的 N 行:每行有三个整数,依次为某种商品的重量、体积和优惠金额,每个数字间以空格分开,所有数值均为不超过 100 的正整数
输出描述:第一行:小惠能够得到的最大优惠金额
第二行:依次为从小到大排列的商品序号,序号从 1 开始,序号间用空格分开。
若第二行输出的序列不唯一,则输出其最小字典序。
样例输入 复制
10 9 4
8 3 6
5 4 5
3 7 7
4 5 4
样例输出 复制
9
2 4