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

简答题

最大购物优惠

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

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

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

编程实现:

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

输入:

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

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

输出:

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

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

样例输入:

样例输出:

9
2 4

样例数据分析:

第一行数据1094代表最多能提起重量10购物袋体积9,4种商品

第二行数据代表第1件商品重量8体积3,让利金额4

第三行数据代表第2件商品重量5,体积4,让利金额5

第四行数据代表第3件商品重量3,体积7,让利金额7

第五行数据代表第4件商品重量4体积5让利金额4

创建一个三维数组 yh[n+1][w+1][v+1] 记录在第n个物品,w重量,v体积时最优策略2

只考虑一个物品的时候(纵向代表重量,横向代表体积,数据代表最大优惠)

考虑前两个物品的时候

考虑前三个物品的时候

考虑前四个物品的时候

最终结果,最大优惠为9.同时需要额外记录在在不同商品数量,不同重量和体积的情况下,如何购买商品

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```#includeusing namespace std;const int maxn=105;int w,v,n,dp[maxn][maxn][maxn],flag[maxn][maxn][maxn];struct nodeint weight,volume,discount;a[maxn];int main()cin>>w>>v>>n;for(int i=1;i<=n;i++) cin>>a[i].weight>>a[i].volume>>a[i].discount;memset(dp,0,sizeof(dp));memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++){for(int j=w;j>=a[i].weight;j--){for(int k=v;k>=a[i].volume;k--){if(dp[j][k] ans;while(i>0&&j>0){ans.push_back(flag[i][j]+1);i-=a[flag[i][j]].weight;j-=a[flag[i][j]].volume;}for(int i=ans.size()-1;i>=0;i--) cout<

解析：

【喵呜刷题小喵解析】：

此题可以使用动态规划的方法来解决。定义dp[i][j][k]为考虑到前i个商品，且当前重量为j，体积为k时，所能获得的最大优惠金额。flag[i][j][k]记录的是dp[i][j][k]对应的商品序号。

首先，对于每个商品，我们遍历所有可能的重量和体积，如果当前商品的重量和体积小于等于当前考虑的重量和体积，且购买当前商品后，所获得的最大优惠金额大于之前考虑的最大优惠金额，则更新dp和flag。

然后，从最后一个商品开始，根据flag的值，将对应的商品序号加入到答案中，并更新当前重量和体积。最后，按照从小到大的顺序输出答案。

需要注意的是，在动态规划的过程中，需要逆向遍历商品，即先遍历到最后一个商品，因为一旦选择了某个商品，就不能再选择它之前的商品了。另外，对于dp和flag的初始化，可以使用memset函数将其初始化为0。

上述代码的时间复杂度为O(n^3)，其中n为商品种类数。

创作类型：

原创

本文链接：最大购物优惠小惠听说超市正在打折促销，要制订一个得到最大优惠的购物计划。小惠的体力可以提起 w

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！