1 条题解
-
0
C++ :
#include <bits/stdc++.h> using namespace std; /* 二维费用背包:创建一个三维数组 yh[n+1][w+1][v+1] 记录在第n个物品,w重量,v体积时 最优策略 二维费用的背包问题,在01背包问题的基础上增加一个费用维度 状态转移方程: dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-w[i]][k-v[i]]+c[i]) */ int w,v,n; //记录有i个物品,承载重量为j,背包容量为k时的最大价值 int dp[110][110][110]; int a[110],b[110],c[110];//分别代表每个物品的重量、体积、让利金额 string r[110][110][110];//代表哪了哪些物品 int main() { //读入数据 cin>>w>>v>>n; for(int i = 1; i <= n; i++) { cin>>a[i]>>b[i]>>c[i]; } for(int i = 0; i <= n; i++) { for(int j = 0; j <= w; j++) { for(int k = 0; k <= v; k++) { r[i][j][k] = ""; } } } //循环物品数量 for(int i = 1; i <= n; i++) { //循环重量 for(int j = 1; j <= w; j++) { //循环体积 for(int k = 1; k <= v; k++) { //承重 和 体积都够,尝试拿这个物品 if(j >= a[i] && k >= b[i]) { dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-a[i]][k-b[i]]+c[i]); //判断该物品是否拿 //拿了 if(dp[i-1][j][k]<dp[i-1][j-a[i]][k-b[i]]+c[i]) { r[i][j][k] = r[i-1][j-a[i]][k-b[i]] + (char)(i + '0') + " "; } else { r[i][j][k] = r[i-1][j][k]; } } else { //没拿 dp[i][j][k] = dp[i-1][j][k]; r[i][j][k] = r[i-1][j][k]; } } } } //最大让利金额 cout<<dp[n][w][v]<<endl; if(r[n][w][v] != "") r[n][w][v] = r[n][w][v].substr(0,r[n][w][v].size()-1); cout<<r[n][w][v];//注意结果会有一个尾随空格 return 0; }
- 1
信息
- ID
- 2769
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者