动规入门：0/1背包

前言

0/1 背包问题，作为动态规划问题的经典问题，可以帮助捋顺思维。之所以叫0/1背包，是因为在这类问题中每种物品只有一个，每个物品只有放和不放两种选择，即对于一种物品，可以表示为0和1两种状态。因此0/1背包统计的是 恒定容量 储存数个 不同物品 的 最大价值。核心在于确认好初始状态、递推基数和递推增量（反正就是dp[i][j-?] + ?，理解万岁）。说白了主要难点还是在确认递推关系上。

一、经典0/1背包问题

有 n(n ≤ 100) 个物品和一个容量为 m(m ≤ 10000) 的背包。

第 i 个物品的容量是 c[i]，价值是 w[i]。现在需要选择一些物品放入背包，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。

1、状态设计

动态规划的最核心之一是确认好dp数组的含义。这决定了你接下来的递推关系和最终问题的返回值。（不知道为什么叫dp数组的自己去查动态规划的英文）每次当你找递推关系出现问题的时候，最好的方法就是回头看一下你确认的dp数组的含义。如果实在找不出，那就要考虑是否在这最开始就出现了问题。

在01背包问题中，我们一般情况下这么设定dp数组：

根据题目要求，我们很容易想到用一对数(i, j)表示前 i 个物品恰好放入容量为 j 的背包 (0 ≤ i < n，0 ≤ j ≤ m)；

因此我们的数组 dp[i][j] 表示状态 (i, j) 下该背包得到的最大价值，即前 i 个物品恰好放入容量为 j 的背包所得到的最大总价值；

2、状态转移方程

列出状态转移方程如下：

dp[i][j]=max(dp[i−1][j],dp[i−1][j−c[i]]+w[i])dp[i][j] = max(dp[i-1][j], dp[i-1][j - c[i]] + w[i])

假设前i-1个物品已经统计完毕，现在正在统计第i个物品的情况。因为每个物品要么放，要么不放，所以只需要考虑两种情况：

1）不放：如果 “第 i 个物品不放入容量为 j 的背包”，那么问题转化成求 “前 i-1 个物品放入容量为 j 的背包” 的问题；由于不放，所以最大价值就等于 “前 i-1 个物品放入容量为 j 的背包” 的最大价值，即 dp[i-1][j]；

2）放：如果 “第 i 个物品放入容量为 j 的背包”，那么问题转化成求 “前 i-1 个物品放入容量为 j-c[i] 的背包” 的问题；那么此时最大价值就等于 “前 i-1 个物品放入容量为 j-c[i] 的背包” 的最大价值，加上放入第 i 个物品的价值，即 dp[i-1][j - c[i]] + w[i]

将以上两种情况取大者，就是我们所求的 “前 i 个物品恰好放入容量为 j 的背包” 的最大价值了。

我知道可能有点绕，这种时候就要请你回去看一下上面状态设计里的内容了。

3、初始状态

既然使用递推关系解决问题，初始状态的正误直接影响了整个问题的正误。

在这个01背包问题中，我们发现，当状态在进行转移的时候，(i, j) 不是来自 (i-1, j)，就是来自 (i-1, j - c[i])，所以必然有一个初始状态，而这个初始状态就是 (0, 0)，含义是 “前 0 个物品放入一个背包容量为 0 的背包”，这个状态下的最大价值为 0，即 dp[0][0] = 0；后续的状态都可以由它递推得出，你可以手动推一下试试就明白了。

我知道可能有点绕，这种时候就要请你回去看一下上面状态设计里的内容了。（梅开二度）

4、非法状态

那么我们再来考虑，如果出现了 (0, 3) ，这是什么意思呢？它代表的是 “前 0 个物品恰好放入一个背包容量为 3 的背包”，明显这种情况是不存在的，因为 0 个物品的价值肯定是 0。所以这种状态被称为非法状态，非法状态是无法进行状态转移的。我们需要对他们也进行初始化。

我知道可能有点绕，这种时候就要请你回去看一下上面状态设计里的内容了。（帽子戏法）

5、状态初始化

dp[0][i]={0i=0xi>0dp[0][i]=\left\{ \begin{aligned} 0&&\text{$i$=0}\\ x &&\text{$i$>0}\\ \end{aligned} \right.

其中 x 在程序实现时，我们可以设定一个非常小的数，比如 -1000000000，只要保证无论如何状态转移它都不能成为最优解的候选状态即可。

二、练习

变形题：416. 分割等和子集 - 力扣（LeetCode）

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

分析

这道题可以换一种表述：给定一个只包含正整数的非空数组nums[]，判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半。这个问题可以转换成「01 背包问题」。

与传统的「01 背包问题」的区别在于，传统的「01 背包问题」要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。类似于传统的「01 背包问题」，可以使用动态规划求解。

在使用动态规划求解之前，首先需要根据数组的长度 n 判断数组是否可以被划分。如果 n<2，则不可能将数组分割成元素和相等的两个子集，因此直接返回 false。其次判断数组元素的和是不是奇数，此时也不可能平分。

由于我们的目的是得知目标是否存在，因此dp数组记录的应该是对于前i个物品，能否组合出和为sum的结果。可以为1，不可以则为0。此时的初始情况如下：

  1. 如果不选取任何正整数，则被选取的正整数等于 0。因此对于所有 0≤i<n，都有 dp[i][0]=true。

  2. 当 i==0 时，只有一个正整数 nums[0] 可以被选取，因此 dp[0][nums[0]]=true。

状态转移方程为：

dp[i][j]={dp[i−1][j]∣dp[i−1][j−nums[i]]j≥nums[i]dp[i−1][j]j<nums[i]dp[i][j]=\left\{ \begin{aligned} dp[i-1][j]|dp[i-1][j-nums[i]]&&\text{$j$≥nums[i]}\\ dp[i-1][j] &&\text{$j$<nums[i]}\\ \end{aligned} \right.

这里出现了一个位运算符或|，不需要我搓个表格告诉你他的作用吧？

想想为什么是这样？（你知道我要说什么.jpg）

根据dp数组的定义，我们可以得知dp[numsSize-1][sum/2]的存在与否就是我们要求的解。

源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool canPartition(int* nums, int numsSize){
    int dp[201][20001], sum = nums[0];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    dp[0][nums[0]] = 1;
    for(int i = 1; i < numsSize; ++i) {
        sum += nums[i];
        for(int j = 0; j < sum; ++j) {
            dp[i][j] = dp[i-1][j];
            if( j - nums[i] >= 0 ) {
                dp[i][j] |= dp[i-1][j - nums[i]];
            }
        }
    }
    if(sum & 1) return false;
    return dp[numsSize-1][sum/2];
}

1262. 可被三整除的最大和 - 力扣（LeetCode）

自己动脑筋吧~（提示一下，同余理论很好用哦！）

要是真的不会，你已经是一个成熟的CSer了，要学会自己寻找答案哦~

本蒟蒻の代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxSumDivThree(int* nums, int numsSize) {
    int dp[40001][3];
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    dp[0][nums[0]%3] = nums[0];
    for(int i = 1; i < numsSize; ++i) {
        for(int j = 0; j < 3; ++j) {
            dp[i][j] = dp[i-1][j];
            int p = ((j - nums[i]%3) + 3) % 3;
            if(dp[i-1][p] != -1) {
                if(dp[i-1][p] + nums[i] > dp[i][j]) {
                    dp[i][j] = dp[i-1][p] + nums[i];
                }
            }
        }
    }
    return dp[numsSize-1][0];
}