1 条题解

  • 0
    @ 2023-6-11 12:24:19

    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
    上传者