A50860. 最大购物优惠小惠听说超市正在打折促销，要制订一个得到最大优惠的购物计划。小惠的体力可以提起 w 单位重量的东西，还有一个能装 V 个单位体积的购物袋，并详细了解了各打折商品的重量、体积及此商品实际优惠的金额。她想在自己体力的限度和购物袋容积限度内，尽可能多地得到购物优惠。超市规定这些打折商品每种只能购买一件。编程实现：请你编写程序，制定一个购买商品的计划，求出小惠能得到的最大优惠金额和实际应购买…
填空题
困难
知识点
题目描述
最大购物优惠
小惠听说超市正在打折促销，要制订一个得到最大优惠的购物计划。
小惠的体力可以提起 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参考答案
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;
const int N=110;
int w[N],v[N],p[N];
int f[N][N][N];
int main()
{
//freopen("shopping.in","r",stdin);
int W,V,n;
cin>>W>>V>>n;
for(int i=1;i<=n;i++) cin>>w[i]>>v[i]>>p[i];
//求最短路，从后往前推
for(int i=n;i>=1;i--){
for(int j=0;j<=W;j++)
for(int k=0;k<=V;k++){
f[i][j][k]=f[i+1][j][k];
if(j>=w[i] && k>=v[i])
f[i][j][k]=max(f[i][j][k],f[i+1][j-w[i]][k-v[i]]+p[i]);
}
}
cout<<f[1][W][V]<<endl;
//字典序向后推
int j=W,k=V;
for(int i=1;i<=n;i++)
if(j>=w[i] && k>=v[i] && f[i][j][k]==f[i+1][j-w[i]][k-v[i]]+p[i]){
cout<<i<<' ';
j-=w[i],k-=v[i];
}
puts("");
return 0;
}答案解析
考察知识:
动态规划,二维费用的背包问题,在01背包问题的基础上增加一个费用维度
状态转移方程:
yh[i][j][k]=max(yh[i-1][j][k],yh[i-1][j-w[i]][k-v[i]]+n[i])
经典01背包问题解(https://blog.csdn.net/qq_38410730/article/details/81667885)
总体思路：
1.先从后往前推，得到最大让利金额，并形成具体方案（仿照最短路问题，从后往前）
2.再从前往后推，得到具体方案的字典序
上一题
下一题