01背包问题-递推公式的自我理解与LeetCode 416. 分割等和子集

学算法好痛苦，完全是对我智力的一次次折磨，看了好多博客，对二维dp数组的理解都是直接搬了代码随想录，搬了随想录又没详细解释，大家都是一眼看懂的吗，好吧（）

一、对二维dp数组的理解

背景

1. 如果有一个容量为j的这样的背包——一个独立的，容量为j的背包。(没把它理解为“剩余容量”)
2. 对于这个背包，可以从编号为0至i的物品里任意挑，挑几个无所谓，挑多重的无所谓
3. 计算第二步挑选的价值，取所有挑选中使整个背包价值最大的这次挑选，将最大的价值记为dp[i][j]
4. 根据前三步，整体的dp[n][m]就是一个n+1行、m+1列的表格。取其中的一格看，比如第i行第j列的dp[i][j]，它的含义为：对于容量为j的背包，编号0-i的物品随便挑，背包最大价值为多少。下面，我们详细说一下dp[i][j]的递推公式。

dp[i][j]的推导

1. dp[i][j]的推导看起来很难，因为要对i+1个物品每个物品0~i都选择放或者不放，那么就有$2^{i+1}$次挑选
2. 但是实际情况下，求dp[i][j]只需要考虑第i个物品的放与不放，也就是对于这个格子只要考虑对于1个物品的2次挑选方式（选与不选）+1次查表（查表——我们遍历表格dp[n][m]的时候已经填写了在dp[i][j]之前的格子，之前的最优挑选查找表格即可。）
3. 为什么可以通过1次查表简化前$2^i$次挑选？

• 首先，不考虑背包容量，如果我们需要dp[i][j]是价值最大的，那么可以分两种情况：在第三步选定“这次挑选”的时候，dp[i][j]【情况1：使整个背包价值最大的这次挑选含第i个物品】，【情况2：使整个背包价值最大的这次挑选不含第i个物品】，那么合起来

dp[i][j]=max{含第i个物品的挑选的背包价值，不含第i个物品的挑选的背包价值}
1

• 其次，再考虑上背包容量，
  ①含第i个物品的挑选的背包价值：由于第i个物品占一定的容量，此时需要调整第0到第i-1个物品的挑选方式。因为需要预留第i个物品的容量，所以对于第0到第i-1个物品，最多只能j-weight[i]的容量，价值为查表得到的dp[i-1][j-weight[i]];对于第i个物品，确定是放，所以再加上它本身的价值value[i]。
  ②不含第i个物品的挑选的背包价值：与dp[i-1][j]相同。因为这种情况等于是从容量为j的背包里选，但只从第0到第i-1个物品里挑。

dp[i][j]
=max{含第i个物品的挑选的背包价值,同样大小的背包不含第i个物品的挑选}
=max{dp[i-1][j],dp[i-1][j-weight[i]]+value[i]}

1
2
3
4

备注：①中还需要判断 j 是否小于 weight[i]，不然j-weight[i]就变成负值，无法成为数组下标。

二、优化：滚动一维数组

如不考虑中间状态，可优化空间复杂度，仅使用j+1个空间，而非（i+1）*(j+1)个。

需要逆序（遍历 j 时），以保证从后往前的时候前面的初始化是没动的，不然dp[j-weight[i]]的计算会用到前面已经加过value[i]的元素，从而再加一个。这个看代码随想录手动推一遍还是比较简单，故不细说。

例1 LeetCode 416. 分割等和子集

由于看了之前的0-1背包，被困住了思路，老是觉得0-1背包是求的一堆元素的“最大值”，而等和子集求的是一堆元素等于某个值的情况，思想上感觉不一样。知道回溯法不配合剪枝肯定不行（200个num，$2^{200}$）
然后隔了一天看了别人没学代码随想录的题解，发现其实很简单，因为我误认为我这里的dp[][]里存放的是和，或者一个特定的值什么的，其实不是，就是单纯的布尔变量，1，或者0。dp[i][j]代表：i个元素，任意选择是否"可"为j?可->1，不可->0，就这么简单。

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
           //元素和相等——>数字集合的和等于1/2 sum
        if (accumulate(nums.begin(), nums.end(), 0) % 2 != 0 || nums.size() == 1)
            return 0;

        int target = accumulate(nums.begin(), nums.end(), 0) / 2;
        vector <vector<int>> dp(nums.size(), vector<int>(target + 1,0));
        //vector> vec(row, vector (col,0)); -- 用 0 来初始化二维vector

        for (int i = 0; i < nums.size(); ++i) {
            dp[i][0] = 1;//均有方法可使得和为0
        }

        for (int j = 1; j <= target; ++j) {
            dp[0][j] = (j == nums[0]);
        }
        for (int i = 1; i < nums.size(); ++i)
        {
            for (int j = 1; j <= target; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j - nums[i] >= 0)
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
            }
            if (dp[i][target] == 1) 
                return 1;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

notes

第一，vector二维数组的初始化问题。如果不手动初始化的话，似乎vector只会初始化一行，所以需要使用vector> vec(row, vector (col,0)); -- 用 0 来初始化二维vector这一行代码，前面是row的数量，后面是col的数量。
第二，dp的初始化。第一次写的时候，初始化很想当然，理清思路以后初始化还是比较简单的。