动态规划背包问题

一、0-1背包问题

现在有一个背包容量为v，有一系列的物品分别有wgt[i]的重量和val[i]的价值。问怎么取物品装到背包里使得总价值最大。

对于每一个物品都有选与不选两种决策，那么对每一个物品进行规划，如果选择了物品，那么可用容量减少但是价值增加。

int dp[n + 1][v + 1];//dp数组
for(int i = 0; i <= n; i++){
    for(int j = 0; j <= v; j++){
        if(i == 0 || j == 0) {
            dp[i][j] = 0;
            break;
        }
        if(j >= wgt[i]) dp[i][j] = max(dp[i - 1][j - wgt[i]] + val[i], dp[i - 1][j]);
        else dp[i][j] = dp[i - 1][j];
    }
}

二、0-1背包空间优化

在01背包中，新dp数值只和上一行相关，所以可以将整体的空间压缩为一行，计算出第一行所有数据之后，计算第二行时要从后往前进行计算。如果从前往后计算，就会提前清除上一行靠前的数据，那么后面的计算就无法使用

int dp[v + 1]; //dp数组
dp[0] = 0; //对特定位置置零
for(int i = 0; i <= n; i ++){
	for(int j = v; j >= 1; j--){
		if(i == 0) dp[j] = 0;
		esle{
			if(j >= wgt[i]) dp[j] = max(dp[j - wgt[i]] + val[i], dp[j]); //如果能放入就由上一行的前面的数据计算得出结果
			else dp[j] = dp[j]; //如果不能放入那么等于原值
		}
	}
}

三、完全背包问题

完全背包和01背包不同之处在于，有无限件可选的物品，也就是说每次进行dp计算时，同一个物品选择后还可以再选一次。但其实整体的思路还是一样的。

int dp[n + 1][v + 1];
for(int i = 0; i <= n; i++){
	for(int j = 0; j <= v; j++){
		if(i == 0 || j == 0) dp[i][j] = 0;
		else{
			if(j >= wgt[i]){
				dp[i][j] = max(dp[i][j - wgt[i]] + val[i], dp[i - 1][j]);//如果选择了放入物品，那么只有容量变化
			}
			else dp[i][j] = dp[i - 1][j]; //如果没有选择那么可选物品进行变化
		}
	}
}

四、完全背包空间优化

完全背包也可以按照01背包类似的思路进行空间优化，但是完全背包的数据不完全来自于上一行数据，也来自于左侧的数据。所以这里采用正序遍历。

dp问题的空间优化关键在于新的数据是否能通过确定步数内的数据推导出**

int dp[v + 1];
dp[0] = 0; //对特定位置置零
for(int i = 0; i <= n; i++){
	for(int j = 0; j<= v; j++){
		if(i == 0) dp[j] = 0;
		else{
			if(j >= wgt[i]) dp[j] = max(dp[j - wgt[i]] + val[i], dp[j]); //如果选择放入物品，数据只和左侧数据有关
			else dp[j] = dp[j]; //如果不选择放入物品，数据就和上一行相同
		}
	}
}

五、多重背包问题

多重背包问题类似完全背包和01背包的思路，综合两者的思路即可解决。在选择一个物品时进行循环，直到物品被取完或者大于背包容量则停止这个物品的选择进入下一个物品的选择。