01背包和完全背包

字数统计: 3.5k字 | 阅读时长: 13分

2020-07-30

摘要: 本文讲解 01 背包和完全背包的算法原理，解决模板题，然后给出一些题目列表

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

背包问题(Knapsack problem)是一种组合优化的NP完全问题。背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

有 n 种物品，物品 i 的体积为 $v_{i}$, 价值为 $w_{i}$, 有一个体积限制 V。如何选择物品使得总体积不超过 V，并使得总价值最大。

这是背包问题最基础的描述，再往下细分还可以把背包问题分成几大类，其中比较基础的是 2 种：01背包，完全背包。

本文对 01 背包和完全背包进行比较详细的讲解，并给出代码实现，然后分别解决 acwing 上的 2 个模板题，以及力扣上的一个例题。

最后我们对力扣上 2000 以内的背包问题进行一个简单的总结，根据问题的问法，大致分为可行方案问题和最优方案问题两大类。练习的时候可以体会一下这两类问题分别怎样与 01 背包和完全背包结合的，详见后面的表格，

$1 01背包

01 背包的问题描述：

有 n 种物品，物品 j 的体积为 $v_{j}$, 价值为 $w_{i}$, 有一个体积限制 V。每种物品只有1个，只有选或者不选, 而没有选几个的问题，此问题称为01背包问题。

最基础的状态设计和状态转移

若只考虑价值尽量大，状态设计是单串线性 DP 中最经典的状态设计：

1	dp[i] := 已经考虑前 i 个物品可以取得的最大价值

由于只考虑价值，则当前物品应该尽量多拿，但是这是错的，因为后面可能有的物品虽然体积大，但是它的价值也很大，由于考虑每个物品时都尽可能多选，轮到后面的物品的时候，可能就没有空间了。

因此状态设计也要考虑体积：

1	dp[i][j] := 已经考虑了 [0..i-1] 前 i 个物品，占用了 j 空间，所能取得的最大价值。

转移方式有两种，一种是放入，一种是不放入。如果放，则前 i - 1 个只能占 j - v[i] 空间，如果不放，则前 i - 1 个物品还是占了 j 空间。

1 2	dp[i][j] = dp[i - 1][j] 当前物品不选 dp[i - 1][j - v[i]] + w[i] 当前物品选，j - v[i] 要大于等于 0

初始化时将所有状态置为 0 即可。这就是 01 背包问题。状态设计和状态转移。一共 $N \times V$ 种状态, 状态的转移 $O(1)$ 可以完成，因此时间复杂度，空间复杂度都是 $O(NV)$。

滚动数组优化需要从后向前枚举

01 背包的状态转移中， i 这一维只跟 i - 1 有关系，因此 i 这一维用滚动数组至少可以将 N 行优化为 2 行。这本来是动态规划的基本操作，在线性动态规划中很常见。这里特别提空间优化是因为 01 背包的 i 这一维用 1 行就可以解决。

假设状态只有一行，即 dp[j] := 占用了 j 空间的情况下可以取到的最大价值, 在推第 i 行的时候，dp 数组中存的是第 i - 1 行的信息。看状态的两个转移方向，第一个是 dp[i - 1][j], 这刚好就是当前 dp 数组在 j 位置保存的数据，因此不用动，比较麻烦的是另一个，就是 dp[i - 1][j - v[i]] + w[i]。这里要用到第 i - 1 行的 dp[j - v[i]]，但是如果按照正常的 j 从 0 到 V 推的话，计算 dp[j] 的时候，dp[j - v[i]] 保存的已经是第 i 行信息了。因此这里需要转换一下，从大往小推，推到 dp[j] 时，dp[j+1], dp[j+2],...,dp[V] 都已经是第 i 行的信息了，但是它们对 dp[j] 的计算没有影响，有影响的 dp[j-v[i]] 此时还是第 i - 1 行的信息，可以满足转移方程 dp[i - 1][j - v[i]] + w[i] 的需要。因此当空间这一维的状态从大往小推的时候，i 这一维状态可以优化到一维。这就是 01 背包的终极形态了。

1	dp[j] = max(dp[j], dp[j - v[i]] + w[i]) // j 从大往小推

要求背包必须放满

如果要求恰好取到背包容量。这个问题可以在 01 背包的基础上改两个地方。

dp 初始化是要初始化为 -1, -1 表示方案不可取。同时 dp[0][0] = 0
状态转移时，dp[i - 1][j - v[i]] + w[i] 要更新进 dp[i][j] 前，先要判断 dp[i - 1][j - v[i]] 是否为 -1，不为 -1，则 dp[i - 1][j - v[i]] 代表的物品组才能放出来

模板题: 278. 数字组合

01背包状态及转移
dp[i][j] := 考虑 [0..i], 体积为 j 的方案数
dp[i][0] = 1
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - v[i]]

倒序枚举 j，省略 i 这一维
dp[j] := 体积为 j 的方案数
dp[0] = 1
dp[j] = dp[j] + dp[j - v[i]]

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for(int i = 0; i < N; ++i)
        cin >> A[i];
    vector<int> dp(M + 1);
    dp[0] = 1;
    for(int i = 0; i < N; ++i)
        for(int j = M; j >= A[i]; --j)
            dp[j] += dp[j - A[i]];
    cout << dp[M] << endl;
}

$2 完全背包

完全背包的问题描述：

有 n 种物品，物品 j 的体积为 $v_{j}$, 价值为 $w_{i}$, 有一个体积限制 V。 每种物品有无限个, 此问题称为完全背包问题。但是由于有体积限制，因此实际取的数量也是有限制的。每个物品其实最多只能取 $V / v[i]$ 个。

朴素想法：拆成 01 背包做

将完全背包强行变成 01 背包：对每个物品 i，都可以求出一个 $V / v[i]$ ，然后就将物品展开，即视为有 $V / v[i]$ 个同样的物品，每个物品有选和不选两种选择。再套用 01 背包的解法可以解决完全背包。

1	dp[j] = max(dp[j], dp[j - v[i]] + w[i]) // j 从大往小推

但是这种办法复杂度太高了，因为物品一下子多了很多，需要优化，最好是不用把物品展开。优化的方法非常巧妙，现在我们不把每个物品展开来考虑这个问题。

不拆物品

首先状态表示与 01 背包相同：

1	dp[i][j] := 已经考虑了 [0..i-1] 前 i 个物品，占用了 j 空间，所能取得的最大价值。

然后考虑的状态转移，对于当前物品 i，也是有两种情况：选和不选。

如果选，在 01 背包中前 i - 1 个只能占 j - v[i] 空间，而在完全背包中因为 i 有无限多个，因此选了 i 之后是前 i 个物品只能占 j - v[i] 空间。
如果不选，则前 i - 1 个物品还是占了 j 空间，这与 01 背包一样。状态转移方程如下，注意唯一的区别就是第 2 行的 dp[i - 1] 变成了 dp[i]

1 2	dp[i][j] = dp[i - 1][j] 当前物品不选 dp[i][j - v[i]] + w[i] 当前物品选，j - v[i] 要大于等于 0

空间优化

考虑空间优化后的状态转移方程如下：在 01 背包中，由于推第 i 行的 dp[j] 时需要第 i - 1 行的 dp[j-v[i]]，因此忌讳在推导 dp[j] 时，dp[j-v[i]]已经更新过了, 这是 01 背包不希望发生的事，解决的办法就是 j 从大往小推。

而上述 01 背包不希望发生的事正是完全背包希望发生的，即推导第 i 行的 dp[j] 时，用到第 i 行的 dp[j -v[i]]。而这仅需要把 01 背包中的从大往小推 j 改为从小往大推 j 即可实现。这就是完全背包的优化巧妙的地方。

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

模板题: 279. 自然数拆分

完全背包状态及转移
dp[i][j] := [0..i] 上，和为 j 的方案数
dp[i][j] = dp[i - 1][j] + dp[i][j - v[i]]
dp[i][0] = 1;

从前往后枚举 j，省略 i 这一维
dp[j] := 和为 j 的方案数
dp[j] = dp[j] + dp[j - v[i]]
dp[0] = 1;

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

const ll MOD = 2147483648;

int main()
{
    int N;
    cin >> N;
    vector<ll> dp(N + 1);
    dp[0] = 1;
    for(int i = 1; i <= N; ++i)
        for(int j = i; j <= N; ++j)
            dp[j] = (dp[j] + dp[j - i]) % MOD;
    cout << (dp[N] - 1 + MOD) % MOD << endl;
}

例题: 322. 零钱兑换

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

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

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

这里我们对力扣上 2000 以内的背包问题进行一个简单的总结。背包问题常见的问法，大致分为可行方案问题、最优方案问题两大类。其中：

可行方案问题又分为可行方案数、判断是否可行等问法，转移方程形式一般为dp[i] = dp[i] + dp[i - num]。
最优方案问题又分为最优方案对应的最值、最优方案数、具体的最优方案等问法，转移方程形式一般为dp[i] = min/max(dp[i], dp[i - num] + 1)。

这两类问法都可以与 01 背包或完全背包结合，需要具体问题具体分析。

写明总结一下背包问题的分析步骤：

分析是否为背包问题。
是可行方案问题、还是最优方案问题。
是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用。
如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法。

下面是题目列表：

题目	问题类型	背包类型	其它特点
494. 目标和	可行方案问题	01 背包	无价值，恰好取得背包容量
377. 组合总和 Ⅳ	可行方案问题	01 背包	无价值，恰好取得背包容量，顺序不同的序列被视作不同的组合
518. 零钱兑换 II	可行方案问题	完全背包	无价值，恰好取得背包容量
面试题 08.11. 硬币	可行方案问题	完全背包	无价值，恰好取得背包容量
879. 盈利计划	可行方案问题	二维费用 01 背包	无价值，第一维费用要求大于等于 P，第二位要求小于等于 G
416. 分割等和子集	可行方案问题	01背包	无价值，判断能否取得背包容量
322. 零钱兑换	最优方案问题	完全背包	恰好取到背包容量
474. 一和零	最优方案问题	二维费用01背包	所有物品价值均为1
1449. 数位成本和为目标值的最大数字	最优方案问题	完全背包	求字典序最大方案
1049. 最后一块石头的重量 II	最优方案问题	01背包	价值就是体积，求可以取到的最大体积(背包剩余容量最小)

这些题目的简要解答可以参考这篇文章：01背包和完全背包题目汇总。

$4 多重背包初探

最后我们提一下多重背包。

有 n 种物品，物品 j 的体积为 $v_{j}$, 价值为 $w_{i}$, 有一个体积限制 V。每种物品还有一个$c_{i}$, 表示每种物品的个数，此问题称为多重背包问题。

多重背包属于比较难的问题，以下仅是主流的思路。详细拆解：多重背包。

朴素想法

将物品展开，全拆成 01。这与完全背包的朴素思路一致。与完全背包的情况一样，这种方法是正确的，但是时间复杂度较高。

朴素想法优化

倍增优化，或者叫二进制优化。

有这样一个事实：任意一个数 n，它一定可以用 1,2,4,8,…$2^{k}$, 以及 $2^{k}$ 到 $2^{k+1}$ 之间的某个数表示。例如 13 以内的所有数都可以用 1,2,4,6 表示。

所以对于物品 i, 数量限制是$c_{i}$ , 可以将其分成若干物品，它们的价值和体积为：($w_{i}$, $v_{i}$), ($2w_{i}$, $2v_{i}$), … 然后对这些物品做 01 背包。这样 01 背包的物品数就比思路 1 少很多了。这可以理解为类似于倍增法的思想。

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

算法动态规划