← 返回题单
题单练习 蓝桥杯STEAM
← 上一题 下一题 →

A70748 | 最大购物优惠

来源编程题
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

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

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

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

输入格式

第一行：依次为 w、v 和 n（n 为商品种类数），所有数值均为不超过 100 的正整数。

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

输出格式

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

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

输入输出样例

输入 #1
10 9 4
8 3 6
5 4 5
3 7 7
4 5 4
输出 #1
9
2 4
输入 #2
20 20 7
5 5 10
6 6 12
7 7 14
4 4 8
3 3 6
8 8 16
2 2 4
输出 #2
40
1 2 3 7
C++ 编辑器
输入
输出