背包问题（01背包、完全背包、多重背包）

背包问题

  问题描述有n件物品，每件物品有一定的价值，获取每件物品都需要一定的代价，在遵守一定的规则的情况下，获取最高的价值。

01背包

规则：每件物品只有1个，要么选，要么不选。
dp[i][j]：当背包容量为j时，从前i件物品中能够获得的最大价值。第i件物品可以不选可以选，如果不选的话dp[i][j]=dp[i-1][j]。如果选择的话，dp[i][j]=dp[i-1][j-w[i]]+v[i]

for(int i=1;i<=n;i++){
	for(int j=0;j<=m;j++){
		if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
			dp[i][j]=max(dp[i][j],dp[i-1][j]);
		}
	}
return dp[n][m];

滚动数组空间优化

for(int i=1;i<=n;i++){  
	for(int j=m;j>=w[i];j--)  
		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);  
	}  
return dp[m]; 

完全背包

完全背包和01背包的区别就是完全背包没件物品可以选择任意次，只需要再加一个for，看当前物品选择多少个才是最合适的。

for(int i=1;i<=n;i++){
	for(int j=0;j<=m;j++)
		for(int k=0;k*v[i]<=j;k++){
			dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+v[i]*k);
		}
	}
return dp[n][m];

优化

优化空间复杂度 假设考虑到第i件物品的容量为j时的状态，即dp[j]，这里的dp[ j ]保存的值是前i-1件物品的最大价值。该怎么转移呢？因为这里对物品选择的个数是没有限制的，所以转移的时候，如果选择1个，那么就从i-1个物品进行转移，选择两个就从再转移一次。所以说转移的dp[j]可以是上一层的也可以是这一层的。，所以遍历的时候，体积正序遍历就可以了。

for(int i=1;i<=n;i++){  
	for(int j=w[i];j<=m;j++)  
		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);  
}  

多重背包

规则：每件物品最多选k次

多重背包也是以01背包为基础的背包问题，最朴素的做法就是枚举该物品的个数，和完全背包的朴素枚举基本上是完全一样的，只需要加一个物品个数限制就可以了。

for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++)
		for(int k=0;k*v[i]<=j&&k<=num[i];k++)
			dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+v[i]*k);
return dp[n][m];

二进制优化

假如说num=10，通过二进制拆分，可以拆分为1+2+4+3。并且这四个数可以组成小于等于10的任意一个数字。因此可以把10个物品拆成四份，每一份为的数目为1,2,4,3。接下来就按照01背包处理就可以了。时间复杂度大约为o(m ) （m是容量，n是物品的个数，c[i]指的是物品i的个数）

int solve1(){
	int n,m;
	cin>>n>>m;
	int pos=0,x,y,z;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>z;
		for(int j=1;z>=j;j<<=1){
			z-=j;
			volume[pos]=j*x;
			value[pos++]=j*y;
		}
		if(z>0) {
			value[pos]=z*y;
			volume[pos++]=z*x;
		}
		}
        for(int i=0;i<pos;i++){
            for(int j=m;j>=volume[i];j--){
                dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
            }
        }
        return dp[m];
}