新手求助,c++,求代码,求助1、京京的购物计划(shopping)问题描述京京的体力可以提起w单位重量的东西,听说玩具超市正在打折促销,他兴冲冲地跑到超市,一一了解了各个玩具的重量、体积及

Question

新手求助,c++,求代码,求助
1、京京的购物计划(shopping)

【问题描述】
京京的体力可以提起w单位重量的东西,听说玩具超市正在打折促销,他兴冲冲地跑到超市,一一了解了各个玩具的重量、体积及此玩具因打折而实际让利的金额.他想在自己体力的限度和网兜容积限度内,尽可能多地得到让利.当然,同一种类的玩具最多购买一件.请你帮京京制定一个购买玩具的计划,告诉他最多能够得到的让利数额及实际应购买的玩具序号.

【输入】
第一行依次为w、v和n(n为玩具种类数)接下去的n行中,每行各有三项数据,依次为某种玩具的重量、体积和让利金额.（shopping.in中所有数据均为不超过100的正整数）

【输出】
输出文件shopping.out的第一行应为京京能够得到的最大让利金额.第二行依次为从小到大排列的玩具序号,序号之间用一个空格分开.

【输入输出样例】

输入
10 9 4

8 3 6

5 4 5

3 7 7

4 5 4
输出
9

2 4

Answer 1

重量限制和容积限制没有主次之分,因此可以直接考虑其中之一取得最优,而另一个不超过限制,即是一个最优解.因此只需要按重量的简单背包来解,最后对结果从最优向下查找第一个容积不超限制的结果即可.也可以增加一个当前容积的数组,边计算边判断.