0-1背包问题（三维dp）

给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi，背包能承受的最大重量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 要求装入物品的总重量不能超出背包能承受的最大重量，装入物品的总体积不能超过背包的容积。在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包能承受的最大重量c，背包的容积d，物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出为最大的总价值。

#include<cstdio>
#include<cmath>
#include <iostream>
const int MAX=99;
int w[MAX],b[MAX],v[MAX],dp[50][50][50],temp;//重量，体积，价值 
//dp[i][j][k]中i代表第1到第i个物品，j代表的是重量，k代表的是容积，dp为对应的最优价值
using namespace std;
int main(){
	int c,d,n,i,j,k;
	int rec[MAX]={0};//用于记录是否被选中，1为选中，0为不选 
	cin>>c>>d>>n;
	for(i=1;i<=n;i++) cin>>w[i]>>b[i]>>v[i];
	for(i=1;i<n+1;i++)
		for(j=1;j<=c;j++)
			for(k=1;k<=d;k++){//此时背包重量为j, 容积为k
				if(w[i]<=j&&b[i]<=k){//当前物品的重量小于背包重量，且体积小于背包容积时，才考虑装入物品的问题
					temp=dp[i-1][j-w[i]][k-b[i]]+v[i];//表示背包装下i物品时的价值
					if(dp[i-1][j][k]>=temp) {//不装i物品的最优价值比装入i物品的最优价值大 
						dp[i][j][k]=dp[i-1][j][k];//不装入
						rec[i]=0; 
					}
					else{
						dp[i][j][k]=temp;//装入i物品 
						rec[i]=1;
					}
				}
				else {
					rec[i]=0;
					dp[i][j][k]=dp[i-1][j][k];//表示背包装不下i物品，最优价值不变，背包状态不变 
				}		
			}
	cout<<"背包能放物品的最大价值为:"<<dp[n][c][d]<<endl;
	cout<<"背包达到最大价值时存放的物品编号为："; 
	for(i=1;i<=n;i++)
		if(rec[i]==1) cout<<i<<" "; 
}

分析思路如下：

背包所能达到最大价值的求解

1. 该问题和一维的背包问题类似，同样具有最优子结构性质，只是增加了一个约束条件，将二维数组变成三维数组，考虑两个变量下的情况，就可以得到该问题的求解方案。
2. 设dp[i][j][k]为物品编号为i，背包承受重量为j，背包容积为k时能达到的最大价值。
3. 对于第i个物品，决策只有两种，一种是第i个物品放入背包，这时dp[i][j][k]= dp[i - 1][j - w[i]][k-b[i]] + v[i]，意为背包减去【第i个物品占用的重量w[i]和体积b[i]】后剩下的容积和重量所能达到的最优价值，再加上【第i个物品的价值v[i]】。
4. 另一种是，第i个物品不放入背包，对于第i个物品不放入背包的情况，dp[i][j] [k]= dp[i - 1][j][k]，此时背包的状态没有发生变化。
5. 综上，dp[i][j][k]应取两种决策结果的最大值，即dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - w[i]][k-b[i]] + v[i])。

背包达到最大价值时所装入物品的编号求解

1. 在求解背包最大价值时可以知道，当第i个物品没有放入背包时，其对应的最大价值dp[i][j][k]仍然等于dp[i-1][j][k] ,此时背包的状态是不变的。
2. 因而可以通过倒序遍历第i个物品对应的dp数组，依次寻找在背包承受重量为c，容积为d时，对应的最大价值是否等于第i-1个物品对应的dp数组的值，来判断第i个物品是否装入了背包。
3. 当第i个物品和第i-1个物品的最优解值相同时，第i个物品没放入背包，否则就是放入背包了。采用x[i]数组记录是否放入，x[i]=1意为i物品放入背包，x[i]=0意为i物品没放入背包。
4. 另外，由于第一个物品没法和上一个物品的最优价值作比较，所以需要单独判断。在此时背包所剩容积与承受重量的情况下，如果其对应的最优价值仍然大于零，那么就意味着第一个物品放入了背包。