背包理论之01背包（滚动数组）

零：背包物品的含义

一：dp数组的含义
dp数组的含义灵活多变，在不同题目中有不同的含义
dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

在遍历过程中，dp数组的含义也不断改变，第一次遍历第一个for，即 i 首先为0时，对应现有物品0时，不同重量背包最大价值，第二次遍历第一个for，即 i 为1时，对应现有物品0,1，不同重量背包最大价值，第二次遍历for就会对数组中的数据进行覆盖（第一次遍历for的操作形成的）。

有两个for，第一个for是 决定选择哪些物品即 0~i类似于选定行，第二个for是依次给数组中的元素赋值 类似于选定列。

for i{
	for j{
		
	}
}
1
2
3
4
5

二：dp数组的递归公式
通过动态规划的含义即当前值可由前一个值推导出，此时就可以联想到，通过是否将最后一个物品添加到背包中进而实现递归公式。

1. 添加最后一个物品即背包容量为 j-weight【i】时的最大价值+value【i】，类似于二维数组dp【i-1】【j-weight【j】】+value【j】，对应于一维数组即：
   dp【j】 = dp【j-weight【j】】+value【j】
2. 不添加最后一个物品即类似于二维数组dp【i-1】【j】，对应于一维数组即本身：
   dp【j】= dp【j】

所以递归公式为：

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

三：一维dp数组的初始化
通过递归公式来判断应该怎样初始化才能达成目的，举例子模拟完整实现过程，进而反推出应该如何初始化。
看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp【j】要么选择原先的dp【j】（即初始化的dp【j】）要么选择新计算的值，会选择两者中较大的那一个。

• 如果dp【j】选择的是新计算的值，dp【j】是从二者中选择更大的值，那么这个初始化的dp【j】就不能够大于新计算的值，新计算的值恒大于0。所以初始化的dp【j】为0即可。

• 若dp【j】选择的是dp【j】（初始化的值）即没有加入物品，初始化后所进行的是第一个物品放入大小为 j 的背包的最大价值，表示的是不加入物品，即一个物品也不加入，那么其价值为0，初始化也应该为0。

四：一维dp数组遍历顺序及i 的含义，j的含义及i，j范围
二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
顺序遍历：
顺序遍历会使本层的dp【i】【j】被覆盖，当前值为上方的一个值和左上方的一个值决定。一维会实现覆盖，顺序遍历时，此时判断物品1在各种背包重量下是否放入的情况，当背包容量为2的时候物品若能放入此时的价值即dp【2】加上了物品1的价值，当背包容量为3的时候物品若能放入此时的价值是dp【2】+value【1】（此时并不一定是dp【2】但一定比3小此时假设为dp【2】），此时的dp【2】是已经覆盖了的dp【2】（添加了物品1的dp【2】）并不是原先那个dp【2】（没有添加物品1的dp【2】）了，此时即表示加入了两次物品1。
逆序遍历：
逆序遍历，是背包容量从大到小遍历，此时判断物品1在各种背包重量下是否放入的情况，当背包容量为3的时候物品若能放入此时的价值是dp【x】+value【1】，x = 3-weight【i】因此x肯定是比3小的，又因为是从后往前遍历的，前面的值是原来的值是没有被覆盖的，覆盖的是当前值后面的值。

两个嵌套for循环的顺序

• 再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？
  因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
  倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。
• 若先遍历物品再嵌套遍历背包容量则具体如下图（纵向一行一行遍历）：
  当前值由上面的值和左上角的值决定，此种情况这两个值都已知。
  
• 若先遍历背包容量再嵌套遍历物品则具体如下图（横向一列一列遍历）：
  当前值由上面的值和左上角的值决定，此种情况遍历某值时左上角的值并不已知，所以不行。
  

从尾到头遍历，同时应该背包重量大于物品重量才进入这个for，即 结束条件 j >= nums[i]而不是j >= 0

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5

一维dp01背包完整C++测试代码

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

int main() {
    test_1_wei_bag_problem();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

适用题型：

• 从数组里面选择元素使得他们之和为某个值，这个情况是否存在
  力扣：416. 分割等和子集
• 从数组里面选择元素使得他们之和为小于等于某个值的最大值
  力扣：1049. 最后一块石头的重量 II
• 从数组里面选择元素使得他们之和为某个值的不同方法
  力扣：目标和
• 从数组里面选择元素（元素有两个性质之和）使得他们的性质之和满足某种条件所需要的最大元素个数。
  力扣：474.一和零