[蓝桥杯省赛 初级组] 最大购物优惠

[蓝桥杯省赛 初级组] 最大购物优惠

时间限制:1 S

内存限制:64 MB

【题目描述】

小惠听说超市正在打折促销,要制定一个得到最大优惠的购物计划。

小惠的体力可以提起 \(w\) 单位重量的东西,还有一个能装 \(v\) 个单位体积的购物袋,并详细了解了各打折商品的重量、体积及此商品实际优惠的金额。她想在自己体力的限度和购物袋容积限度内,尽可能多地得到购物优惠。

超市规定这些打折商品每种只能购买一件。

请你编写程序,制定一个购买商品的计划,求出小惠能得到的最大优惠金额和实际应购买的各商品序号。

【输入格式】

第一行:依次为 \(w\) 、\(v\) 和 \(n\)(\(n\) 为商品种类数),所有数值均为不超过 \(100\) 的正整数。

接下来的 \(n\) 行:每行有三个整数,依次为某种商品的重量、体积和让利金额,数值间以空格分开,所有数值均为不超过 \(100\) 的正整数。

【输出格式】

第一行:小惠能够得到的最大让利金额。

第二行:依次为从小到大排列的商品序号,序号从 \(1\) 开始,序号间用空格分开。若第二行输出的序列不唯一,则输出其最小字典序。

样例 1

【样例 1 输入】

10 9 4
8 3 6
5 4 5
3 7 7
4 5 4

【样例 1 输出】

9
2 4

信息

ID
1021
难度
2
分类
(无)
标签
递交数
28
已通过
1
通过率
4%
上传者