01背包和完全背包题目汇总

字数统计: 4.8k字 | 阅读时长: 22分

2020-11-25

摘要: 转换为 01 背包和完全背包的组合问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

组合数学的问题有时候可以转换为背包问题进而解决，而组合数学研究组合的存在性、计数性、优化性。也就是说背包问题可以解决某些类型的组合存在、组合计数、组合优化问题。这类问题在力扣中不少，本文针对这些问题做个小结。以下是内容总览：

优化问题：求最大价值
组合问题：求方案数(不一定是最优决策)
- 494. 目标和
- 377. 组合总和 Ⅳ
  - 组合相同但顺序不同被视作不同的方案
- 518. 零钱兑换 II
- 面试题 08.11. 硬币
- 879. 盈利计划
  - 二维费用，且费用约束为上界或下界而不是恰好取到
组合问题：求可行性
- 416. 分割等和子集

本文的题解中，只要将转换成背包问题后的背包、物品、价值、重量的含义列清楚，就可以视为解决了，直接给出代码。之后就是用 01 背包和完全背包的算法解决就好，参考文章 01背包和完全背包。

$1 优化问题：求最大价值

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

提示：

1
2
3

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 1e4

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

算法：完全背包

完全背包恰好取到背包容量的最小价值。
所有物品价值均为 1。

代码 (C++)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        using ll = long long;
        if(coins.empty()) return 0;

        int N = coins.size();
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < N; ++i)
            for(int j = coins[i]; j <= amount; ++j)
                dp[j] = min((ll)dp[j], (ll)dp[j - coins[i]] + 1);
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

474. 一和零

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

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

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

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

示例 1：
输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：
输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

算法：01背包

二维费用01背包。
所有物品价值均为 1。

代码 (C++)

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        if(strs.empty()) return 0;
        int N = strs.size();
        int V1 = m, V2 = n; // 二维费用背包的两个容量

        vector<int> v1(N, 0); // 0 个数
        vector<int> v2(N, 0); // 1 个数
        for(int i = 0; i < N; ++i)
        {
            string str = strs[i];
            for(char c: str)
            {
                if(c == '0')
                    ++v1[i];
                else
                    ++v2[i];
            }
        }

        vector<vector<int> > dp(V1 + 1, vector<int>(V2 + 1, 0));
        for(int i = 0; i < N; ++i)
            for(int j = V1; j >= v1[i]; --j)
                for(int k = V2; k >= v2[i]; --k)
                    dp[j][k] = max(dp[j][k], dp[j - v1[i]][k - v2[i]] + 1);

        return dp[V1][V2];
    }
};

1449. 数位成本和为目标值的最大数字

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的最大整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

提示：

1
2
3

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

示例 1：
输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出：”7772”
解释：添加数位 ‘7’ 的成本为 2 ，添加数位 ‘2’ 的成本为 3 。所以 “7772” 的代价为 23+ 31 = 9 。 “977” 也是满足要求的数字，但 “7772” 是较大的数字。
数字成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5

示例 2：
输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出：”85”
解释：添加数位 ‘8’ 的成本是 7 ，添加数位 ‘5’ 的成本是 5 。”85” 的成本为 7 + 5 = 12 。

示例 3：
输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出：”0”
解释：总成本是 target 的条件下，无法生成任何整数。

示例 4：
输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出：”32211”

算法：完全背包

完全背包
求最大价值
求字典序最大方案

代码 (C++)

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        int n = cost.size();
        vector<vector<int>> dp(n, vector<int>(target + 1, -1));
        for(int i = 0; i < n; ++i)
            dp[i][0] = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 1; j <= target; ++j)
            {
                if(i > 0)
                    dp[i][j] = dp[i - 1][j];
                if(j - cost[i] >= 0 && dp[i][j - cost[i]] != -1)
                    dp[i][j] = max(dp[i][j], dp[i][j - cost[i]] + 1);
            }
        }
        if(dp[n - 1][target] == -1)
            return "0";
        string result;
        int i = 8;
        int j = target;
        while(j > 0)
        {
            if(j - cost[i] >= 0 && dp[i][j - cost[i]] + 1 == dp[i][j])
            {
                j -= cost[i];
                result += '0' + i + 1;
            }
            else
                --i;
        }
        return result;
    }
};

1049. 最后一块石头的重量 II

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

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

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

提示：

1 2	1 <= stones.length <= 30 1 <= stones[i] <= 100

示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：
输入：stones = [31,26,33,21,40]
输出：5

算法：01背包

01背包
物品价值就是物品体积(求可以取到的最大体积(背包剩余容量最小))

分成两堆，使得两堆的和的差最小。

转换为01背包问题，背包容量 V 为石子重量总和除以2。

j体积为石子重量
j价值也为石子重量
在体积 <= V 的条件下取最大价值

dp[i][j] := 考虑前 i 件物品，且背包容量为 j 时所能获得的**最大价值**

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); 第一项是不选 i, 第二项是选 i(j - v[i] >= 0)
其中 w[i] = v[i]

代码 (C++)

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int W = 0;
        for(int i: stones) W += i;
        int target = W / 2;
        // 使得和 小于等于 target 同时尽可能接近 target
        vector<int> &v = stones; // 物品体积
        int &V = target; // 背包容量
        int n = v.size();
        // dp[i][j] := 考虑前 i 件中，容量为 j，能取到的最大体积
        vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
        for(int i = 1; i <= n; ++i)
            for(int j = V; j >= 0; --j)
            {
                dp[i][j] = dp[i - 1][j]; // 不选 i
                if(j - v[i - 1] >= 0) // 选 i
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1]] + v[i - 1]);
            }
        return W - 2 * dp[n][V];
    }
};

$2 组合问题：求方案数(不一定是最优决策)

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：
输入：nums = [1], target = 1
输出：1

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

算法：01背包

01 背包
恰好取得背包容量
无价值
求方案数

代码 (C++)

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (!(-sum <= S && S <= sum))
            return 0;

        vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0));
        dp[0][0 + sum] = 1;

        for(int i = 1; i <= n; i++)
            for (int j = -sum; j <= sum; j++)
            {
                if(-sum <= j - nums[i - 1])
                    dp[i][j + sum] += dp[i - 1][j - nums[i - 1] + sum];
                if(j + nums[i - 1] <= sum)
                    dp[i][j + sum] += dp[i - 1][j + nums[i - 1] + sum];
            }

        return dp[n][S + sum];

    }
};

377. 组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：
输入：nums = [9], target = 3
输出：0

算法：01背包

01 背包
恰好取得背包容量
无价值
组合相同但顺序不同被视作不同的方案

(a)组合相同但顺序不同被视作不同的方案与(b)组合相同但顺序不同被视作相同的方案的唯一区别

(a)组合相同但顺序不同被视作不同的方案，先枚举体积再枚举物品
(b)组合相同但顺序不同被视作相同的方案，先枚举物品再枚举体积

1
2
3

dp[j] := 容量为 j 的方案数
dp[0] = 1
dp[j] = sum(dp[j - v[i]])  j - v[i] >= 0

代码 (C++)

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        const int MOD = INT_MAX;
        using ll = long long;
        int n = target;
        if(n == 0) return 1;
        vector<ll> dp(n + 1, 0);
        dp[0] = 1;
        const vector<int> &v = nums;
        int m = v.size();
        for(int j = 1; j <= n; ++j)
        {
            for(int i = 0; i < m; ++i)
                if(j - v[i] >= 0)
                    dp[j] = (dp[j] + dp[j - v[i]]) % MOD;
        }
        return dp[n];
    }
};

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

提示：

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000

示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：
输入：amount = 10, coins = [10]
输出：1

算法：完全背包

完全背包
恰好取得背包容量
无价值
求方案数

代码 (C++)

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // if(amount == 0) return 1;
        int N = coins.size();

        vector<int> dp(amount + 1, INT_MIN);
        dp[0] = 0;
        vector<int> g(amount + 1, 0);
        g[0] = 1;

        for(int i = 0; i < N; ++i)
            for(int j = coins[i]; j <= amount; ++j)
            {
                int s = 0;
                int t = max(dp[j], dp[j - coins[i]]);
                if(dp[j] == t) s += g[j];
                if(dp[j - coins[i]] == t) s += g[j - coins[i]];
                g[j] = s;
                dp[j] = t;
            }
        if(g[amount] == INT_MIN) return 0;
        return g[amount];
    }
};

面试题 08.11. 硬币

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

注意:

1	0 <= n (总金额) <= 1000000

示例1:
输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2:
输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

算法：完全背包

完全背包
恰好取得背包容量
无价值
求方案数

1
2
3

dp[j] := 容量为 j 的方案数
dp[0] = 1
dp[j] = sum(dp[j - v[i]])  j - v[i] >= 0

代码 (C++)

class Solution {
public:
    int waysToChange(int n) {
        if(n == 0) return 1;
        using  ll = long long;
        const int MOD = 1e9 + 7;
        vector<ll> dp(n + 1, 0);
        dp[0] = 1;
        const vector<int> v({25, 10, 5, 1});
        int m = v.size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 1; j <= n; ++j)
                if(j - v[i] >= 0)
                    dp[j] = (dp[j] + dp[j - v[i]]) % MOD;
        }
        return dp[n];
    }
};

879. 盈利计划

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为盈利计划。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以返回结果模 10^9 + 7 的值。

提示：

1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

示例 1：
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。

示例 2：
输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

算法：01背包

每种犯罪是一种物品。

二维费用 01 背包
第一维费用: 产生的利润，要求大于等于 P
第二维费用: 占用的人数，要求小于等于 G
无价值
求方案数

代码 (C++)

struct Item
{
    int p, g;
    Item(int p, int g):p(p),g(g){}
};

struct Cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.p > i2.p;
    }
};

class Solution {
public:
    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
        int n = profit.size();
        // dp[i][j][k] := 剩余[i..n - 1], G = j, P = k 方案数
        vector<Item> items;
        for(int i = 0; i < n; ++i)
            items.push_back(Item(profit[i], group[i]));
        sort(items.begin(), items.end(), Cmp());
        vector<int> remain(n, 0); // [i..n-1] 剩余的总利润
        remain[n - 1] = items[n - 1].p;
        for(int i = n - 2; i >= 0; --i)
            remain[i] = remain[i + 1] + items[i].p;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(G + 1, vector<int>(P + 1, -1)));
        return solve(0, G, P, items, dp, remain);
    }

private:
    const int MOD = 1e9 + 7;
    using ll = long long;

    int solve(int i, int j, int k, const vector<Item>& items,
            vector<vector<vector<int>>>& dp, const vector<int>& remain)
    {
        if(dp[i][j][k] != -1)
            return dp[i][j][k];

        int n = items.size();
        if(i == n - 1)
        {
            dp[i][j][k] = 0;
            if(k == 0) ++dp[i][j][k];
            if(items[i].p < k || items[i].g > j)
                return dp[i][j][k];
            else
                return ++dp[i][j][k];
        }

        if(remain[i] < k)
            return dp[i][j][k] = 0;

        if(j == 0)
        {
            if(k == 0)
                return dp[i][j][k] = 1;
            else
                return dp[i][j][k] = 0;
        }

        dp[i][j][k] = solve(i + 1, j, k, items, dp, remain);
        if(j >= items[i].g)
            dp[i][j][k] = ((ll)dp[i][j][k] + solve(i + 1, max(0, j - items[i].g), max(0, k - items[i].p), items, dp, remain)) % MOD;
        return dp[i][j][k];
    }
};

$3 组合问题：求可行性

416. 分割等和子集

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

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

1 2	1 <= nums.length <= 200 1 <= nums[i] <= 100

算法：01背包

01背包
无价值
判断能否取得背包容量

代码 (C++)

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int N = nums.size(); // 背包问题物品数
        if(N < 2) return false;
        int V = 0;
        for(int num: nums) V += num;
        if(V & 1) return false;
        V /= 2; // 背包问题的容量
        vector<int> &v = nums; // 每个物品的体积
        vector<int> dp(V + 1, INT_MIN); // 需要体积恰好取到容量，所以要初始化为负无穷
        dp[0] = 0;
        for(int i = 0; i < N; ++i)
            for(int j = V; j >= v[i]; --j)
                dp[j] = max(dp[j], dp[j - v[i]] + 1);
        return dp[V] > 0;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法动态规划

01背包和完全背包题目汇总

$1 优化问题：求最大价值

322. 零钱兑换

算法：完全背包

代码 (C++)

474. 一和零

算法：01背包

代码 (C++)

1449. 数位成本和为目标值的最大数字

算法：完全背包

代码 (C++)

1049. 最后一块石头的重量 II

算法：01背包

代码 (C++)

$2 组合问题：求方案数(不一定是最优决策)

494. 目标和

算法：01背包

代码 (C++)

377. 组合总和 Ⅳ

算法：01背包

代码 (C++)

518. 零钱兑换 II

算法：完全背包

代码 (C++)

面试题 08.11. 硬币

算法：完全背包

代码 (C++)

879. 盈利计划

算法：01背包

代码 (C++)

$3 组合问题：求可行性

416. 分割等和子集

算法：01背包

代码 (C++)