背包问题(0-1)学习心得

首先声明本文章为本人学习心得体会，仅供个人总结使用。如有错误，欢迎大家指正。

背包问题(0-1)

有a个物体和容量为b的背包，每个物体有对应的重量与价值，当背包装满时，最大价值为多少？

二维数组解法

1. 确定二维数组含义

   • 二维数组dp的含义：0-i个物品任选放进容量为j的背包的最大价值
   • i就代表0-i个物品任意选
   • j则代表背包的容量

2. 确定递推公式(即如何通过上一个位置的值得到下一个位置的值)

   • dp数组有两种状态，一个是放第i个物品得到其价值，另一个则是背包容量不够，不放第i个物品

		dp[i][j] = dp[i-1][j]; // 不放物品i
		dp[i][j] = dp[i-1][j - weight[i]] + value[i];// 放物品i

		// 递推公式
		dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. 数组如何初始化

   • dp[][0]当背包容量为0时候什么东西都放不下，所以这一列肯定都初始化为0
   • dp[0][]当物品0存放时，如果容量小于物品0的重量则肯定为0，容量大于等于物品0的重量则都为物品0的价值
   • 其余位置就随便初始化了，不过为了方便起见，个人认为统一初始化为0比较好

4. 遍历顺序

   • 先遍历物品或者是先遍历背包都可以，但是二者在数组中移动的方向不太一样

// 先遍历物品
// weight数组的大小就是物品个数，当然用value数组也可以
// 因为dp[0][0]已经初始化过了，所以直接从1开始
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 1; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]){
	        dp[i][j] = dp[i - 1][j];
        } 
        else{
	        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        } 
    }
}

// 先遍历背包
for(int j = 1; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]){
	        dp[i][j] = dp[i - 1][j];
        }
        else{
	        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        } 
    }
}

一维数组解法

其实一维数组的解法和二维数组的解法本质上是相同的，因为二维数组其实就是由多个一维数组组成，我们用二维数组解决这个问题的时候是由上一个状态推导而来，而一维数组只不过就是上一个状态和下一个状态的值会放在同一个位置上。

• dp数组含义：容量为j的背包，所背的物品价值可以最大为dp[j]
• 推导公式：因为变成了一维数组，所以推导公式就变为了

	dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

• 初始化：其实初始化还是一样的，我们把整个一维数组初始化过后就可以进行相应的推导了(因为初始化后的值就相当于是上一状态)
• 遍历顺序：一维数组的方式就只能先遍历物品再遍历背包，且必须倒序遍历。因为正序遍历可能会存在一个物品被放入多次。

最后希望本文章能够让你有所收获~