0-1背包问题笔记

一、原始版本

0-1背包问题的原始版本为：

有N件物品和一个最大容纳重量为W的背包。第i件物品的重量是weights[i]，价值是values[i] ，每件物品只能用一次，问将哪些物品装入背包之后物品的总价值最大。

通用的解题模板为：设计一个二维数组dp[N+1][W+1]，使用两层循环遍历，最后返回二维数组的最后一个值，代码如下。

vector<vector<int>> dp(N + 1, vector<int> (W + 1, 0));
// 此处dp[i][j]的含义为：遍历完前i个物体之后，背包中所装物体重量不超过W时的物品的总最大价值

for (int i = 1; i <= N; ++i) {
    for (int w = 0; w <= W; ++w) {
        // 注意weights与values访问时下标i需要减去1，因为i取值是1～N，而这两个数组的下标取值是0～N-1
        dp[i][w] = dp[i - 1][w]; // 不选第i个物品
        if (w >= weights[i - 1]) {
            dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); // 选第i个物品
        }
    }
}

return dp[N][W];

上述代码是我刚刚总结出来的，还没测试过，因为实际做题中遇到的都是原始题目的变体，代码实现上会有细微的差异，很容易转不过弯来。

可能需要修改的地方包括但不限于：

数组第一维的大小（是否需要+1）
数组第二维的大小
外层循环的遍历范围
是否需要初始化dp[0]、如何初始化
返回值的选取
dp[i][w]选用的是max还是min，还是bool值

二、“恰好”版：LeetCode 416 分割等和子集

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

首先进行映射：

物品=>数
物品重量=>数值大小
物品总价值=>并不是一个求和结果，而是一个bool值，表示是否存在一种取法，使得物体总重量为该值

问题转换为：有nums.size()个物品，其重量为nums[i]，每个物品可放入背包也可不放入背包，求是否存在某一种取法，使得背包内的物品总重量恰好为sum(nums) / 2。

代码实现：

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
    }
    if (sum % 2) {
        return false;
    }

    vector<vector<int>> dp(nums.size(), (vector<int> (sum + 1, 0)));
    dp[0][nums[0]] = 1;
    dp[0][0] = 1;
    for (int i = 1; i < nums.size(); ++i) {
        for (int w = 0; w <= sum / 2; ++w) {
            if (dp[i - 1][w] || (w >= nums[i]) && dp[i - 1][w - nums[i]]) {
                dp[i][w] = 1;
            }
        }
    }
    return dp[nums.size() - 1][sum / 2];
}

代码细节：

dp[i][j]的含义为：遍历完前i个物体之后，是否存在背包重量恰好为j的情况
数组第一维大小不需要加1，下标从0开始，遍历时跳过第0个
dp[0]需要进行初始化。两行初始化语句表示：遍历完第一个物体之后，背包容量要么为0，要么为第一个物体的重量
dp[i][w]的求法：只要取第i个或者不取第i个这两种取法的其中一种是合法的，dp[i][j]就为真
内层循环需遍历到num / 2

三、“恰好”版：LeetCode 1049 最后一块石头的重量

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

int lastStoneWeightII(vector<int>& stones) {
    int sum = 0;
    for (int i = 0; i < stones.size(); ++i) {
        sum += stones[i];
    }

    vector<vector<int>> dp(stones.size(), (vector<int> (sum + 1, 0)));
    dp[0][stones[0]] = 1;
    dp[0][0] = 1;
    for (int i = 1; i < stones.size(); ++i) {
        for (int w = 0; w <= sum; ++w) {
            if (dp[i - 1][w] || (w >= stones[i]) && dp[i - 1][w - stones[i]]) {
                dp[i][w] = 1;
            };
        }
    }

    double sum_db = sum;
    double minVal = INT_MAX;
    for (int w = 0; w <= sum; ++w) {
        if (dp[stones.size() - 1][w])
            minVal = min(minVal, abs(w - sum_db / 2));
    }
    return minVal * 2;
}

与上一题完全相同。这道题难在如何将题干转换成0-1背包问题。

四、双背包版：LeetCode 474 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

我的思路非常朴素，多一个背包相当于给dp数组加一个维度，多套一层循环进行遍历。

这是我的错误解答：

int findMaxFormIncorrectSolution(vector<string>& strs, int m, int n) {
    // 错误解答
    vector<vector<int>> nums(strs.size(), vector<int> (2, 0));

    for (int i = 0; i < strs.size(); ++i) {
        for (int j = 0; j < strs[i].size(); ++j) {
            if (strs[i][j] == '0') ++nums[i][0];
            else ++nums[i][1];
        }
    }

    vector<vector<vector<int>>> dp(strs.size(), vector<vector<int>> (m + 1, vector<int> (n + 1, 0)));
    if (nums[0][0] <= m && nums[0][1] <= n)
        dp[0][nums[0][0]][nums[0][1]] = 1;
    for (int i = 1; i < strs.size(); ++i) {
        for (int w0 = 0; w0 <= m; ++w0) {
            for (int w1 = 0; w1 <= n; ++w1) {
                int maxVal = 0;
                if (w0 >= nums[i][0] && w1 >= nums[i][1]) {
                    maxVal = 1 + dp[i - 1][w0 - nums[i][0]][w1 - nums[i][1]];
                }
                maxVal = max(maxVal, dp[i - 1][w0][w1]);
                dp[i][w0][w1] = maxVal;
            }
        }
    }

    return dp[strs.size() - 1][m][n];
}

错误原因在于：我受到了“恰好”版的影响，以为需要初始化dp[0]；但这道题更接近于原始版本，不需要初始化，数组第一维的长度相应地要加1，对nums数组的访问下标需要减1。因为题干提到了“最多有 m 个 0 和 n 个 1 ”，所以dp数组的值表示的是背包重量不超过第二维和第三维时的最大价值，与原始版本题意相同，只是多了一维。

正确解答：

int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> nums(strs.size(), vector<int> (2, 0));

    for (int i = 0; i < strs.size(); ++i) {
        for (int j = 0; j < strs[i].size(); ++j) {
            if (strs[i][j] == '0') ++nums[i][0];
            else ++nums[i][1];
        }
    }

    vector<vector<vector<int>>> dp(strs.size() + 1, vector<vector<int>> (m + 1, vector<int> (n + 1, 0)));
    for (int i = 1; i <= strs.size(); ++i) {
        for (int w0 = 0; w0 <= m; ++w0) {
            for (int w1 = 0; w1 <= n; ++w1) {
                int maxVal = 0;
                if (w0 >= nums[i - 1][0] && w1 >= nums[i - 1][1]) {
                    maxVal = 1 + dp[i - 1][w0 - nums[i - 1][0]][w1 - nums[i - 1][1]];
                }
                maxVal = max(maxVal, dp[i - 1][w0][w1]);
                dp[i][w0][w1] = maxVal;
            }
        }
    }

    return dp[strs.size()][m][n];
}

五、总结

原始版本：数组第一维长度N+1，外层循环从1遍历到N，无需初始化（准确地说应该是全部初始化为0）
恰好版本：数组第一维长度N，外层循环从1遍历到N-1，需初始化dp[0]，把恰好取第一个物体和不取第一个物体两种情况考虑进去
双背包版本：在上述基础上，给数组加一个维度

如果实在不想微调第一维的下标，想统一前两种情况，那么在原始版本当中，需要将dp[0][j], j >= weights[0]初始化为values[0]，之后就可以用”恰好“版的方式进行遍历。