Leetcode记录：0-1背包问题

27 Aug 2024

0-1背包理论基础

背包问题分类如下图：

0-1背包问题指的是有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维dp数组01背包

dp数组含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
dp递推公式推导由两部分构成：
1. 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。
2. 放物品i：由dp[i - 1][j - weight[i]]推出，即背包容量为j - weight[i]的时候不放物品i的最大价值。因此递推公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。
dp初始化：如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当 j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
遍历顺序：因为递推只需要左上角和正上方的值，因此先遍历物品还是背包都可以，但是先遍历物品再遍历背包这个顺序更好理解。

要注意 j < weight[i] 时候也要状态转移

int main() {
    int n, bagweight;// bagweight代表行李箱空间
    cin >> n >> bagweight;
    vector<int> weight(n, 0); // 存储每件物品所占空间
    vector<int> value(n, 0);  // 存储每件物品价值
    for(int i = 0; i < n; ++i) {
        cin >> weight[i];
    }
    for(int j = 0; j < n; ++j) {
        cin >> value[j];
    }
    // dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化, 因为需要用到dp[i - 1]的值
    // j < weight[0]已在上方被初始化为0
    // j >= weight[0]的值就初始化为value[0]
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    for(int i = 1; i < weight.size(); i++) { // 遍历科研物品
        for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    cout << dp[n - 1][bagweight] << endl;
    return 0;
}

一维dp数组

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])。 与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。此时：

一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
初始化均为0即可。

注意遍历顺序：外层遍历物品，内层倒序遍历容量,是为了保证物品i只被放入一次：

 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]);

     }
 }

0-1背包例题

问题主要分为 能否能装满背包、装满背包有几种方法、背包装满最大价值、装满背包所有物品的最小个数

分割等和子集

Leetcode 416. 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

背包的体积为sum / 2；背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值；背包如果正好装满，说明找到了总和为 sum / 2 的子集；背包中每一个元素是不可重复放入。

bool canPartition(vector<int>& nums) {
    int sum = 0;

    // dp[i]中的i表示背包内总和
    // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
    // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
    vector<int> dp(10001, 0);
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
    }
    // 也可以使用库函数一步求和
    // int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 == 1) return false;
    int target = sum / 2;

    // 开始 01背包
    for(int i = 0; i < nums.size(); i++) {
        for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    // 集合中的元素正好可以凑成总和target
    if (dp[target] == target) return true;
    return false;
}

最后一块石头的重量II

有一堆石头，每块石头的重量都是正整数。每一回合，从中选出任意两块石头，然后将它们一起粉碎。最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

将石头分为两部分，将一部分记为neg，则有尽可能让sum-2neg最小：

int lastStoneWeightII(vector<int>& stones) {
    vector<int> dp(15001, 0);
    int sum = 0;
    for (int i = 0; i < stones.size(); i++) 
        sum += stones[i];
    int target = sum / 2;
    for (int i = 0; i < stones.size(); i++) { 
        // 遍历物品
        for (int j = target; j >= stones[i]; j--) { // 遍历背包
            dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }
    return sum - dp[target] - dp[target];
}

目标和

Leetcode 494. 给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

依然是sum - 2neg = target –> neg = (sum - target) / 2. 此时问题就转化为，装满容量为x的背包，有几种方法。

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法; dp[j] += dp[j - nums[i]]; 初始化的时候dp[0]应该为1，因为只有不取任何元素才为0； 01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。

int findTargetSumWays(vector<int>& nums, int target) {
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) sum += nums[i];
    if (abs(target) > sum) return 0; // 此时没有方案
    if ((target + sum) % 2 == 1) return 0; // 此时没有方案
    int bagSize = (target + sum) / 2;
    vector<int> dp(bagSize + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = bagSize; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[bagSize];
}

1和0

Leetcode 474. 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。

本题中strs 数组里的元素就是物品，每个物品都是一个！而m 和 n相当于是一个背包，两个维度的背包。但本质上还是0-1背包问题，只不过容量分为两个维度而已。

int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
    for (string str : strs) { // 遍历物品
        int oneNum = 0, zeroNum = 0;
        for (char c : str) {
            if (c == '0') zeroNum++;
            else oneNum++;
        }
        for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
            for (int j = n; j >= oneNum; j--) {
                dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
            }
        }
    }
    return dp[m][n];
}

完全背包问题

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的，所以要从小到大去遍历。 也可以从二维dp数组的角度来解释，此时的状态转移方程变为dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+value[i])。

问题主要分为求组合数、求排列数、求最小数。

零钱兑换II 遍历顺序

Leetcode 518. 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

当求组合数的时候，就是先遍历物品，再遍历背包：

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        for (int j = coins[i]; j <= amount; j++) { // 遍历背包
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

组合总和 IV

Leetcode 377. 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

此时要找的是排列个数，就要先遍历背包，再遍历物品：

int combinationSum4(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int i = 0; i <= target; i++) { // 遍历背包
        for (int j = 0; j < nums.size(); j++) { // 遍历物品
            if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                dp[i] += dp[i - nums[j]];
            }
        }
    }
    return dp[target];
}

爬楼梯

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

也可以转化为一个完全背包问题，楼顶就是背包，阶数就是物品：

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) { // 遍历背包
            for (int j = 1; j <= m; j++) { // 遍历物品
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        cout << dp[n] << endl;
    }
}

零钱兑换

Leetcode 322. 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        for (int j = coins[i]; j <= amount; j++) { // 遍历背包
            if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
                dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
            }
        }
    }
    if (dp[amount] == INT_MAX) return -1;
    return dp[amount];
}

完全平方数

Leetcode 279. 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 0; i <= n; i++) { // 遍历背包
        for (int j = 1; j * j <= i; j++) { // 遍历物品
            dp[i] = min(dp[i - j * j] + 1, dp[i]);
        }
    }
    return dp[n];
}

单词拆分

Leetcode 139. 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

也可以看作是一个完全背包问题：

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (int i = 1; i <= s.size(); i++) {   // 遍历背包
        for (int j = 0; j < i; j++) {       // 遍历物品
            string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
            if (wordSet.find(word) != wordSet.end() && dp[j]) {
                dp[i] = true;
            }
        }
    }
    return dp[s.size()];
}

数据结构与算法