动态规划之背包问题

发表于 更新于 本文字数： 3.7k 阅读时长 ≈ 3 分钟

动态规划之背包问题

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

也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V。

定义

我们有n种物品，物品i的重量为wi，价值为vi

我们假定所有物品的重量和价值都是非负数，背包所能承受的最大重量为W。

  • 如果限定每种物品最多能选择1个，则该背包称为01背包。

    可以用公式表示为：

$$ \begin{align} 最大化 & \quad \sum^{n}_{i=1}{v_{i} x_i} \\ 受限于 & \quad \sum^{n}_{i=1}{w_{i} x_i} \leq W, \quad x_i \in \{0,1\} \\ \end{align} $$

  • 如果限定物品i最多只能选择bi个，则问题称为多重背包问题（有界背包问题）。

    可以用公式表示为： $$ \begin{align} 最大化 & \quad \sum^{n}_{i=1}{v_{j} x_i} \\ 受限于 & \quad \sum^{n}_{i=1}{w_{i} x_i} \leq W, \quad x_i \in \{0,1…,b_i \} \\ \end{align} $$

  • 如果不限定每种物品的数量，则问题称为完全背包问题（无界背包问题）。

  • 各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。

01背包

设一共有N件物品，第i件物品的重量为w[i]，价值为v[i]，最大总重量为W。

如果采取暴力枚举方法，每件物品都存在装入和不装入两种情况，所以时间复杂度为O(2n)，使用动态规划可以把时间复杂度控制在O(N * W)。求解的总目标是背包物品的总价值，变量有是否放入物品和书包限重。

定义dp[i][j]表示将前i件物品放入限重为j的书包可以获得的最大价值，其中0 ≤ i ≤ N, 0 ≤ j≤ W。

状态转移：

  1. 不装入第i物品：dp[i][j] = dp[i − 1][j]
  2. 在能装入的前提下，装入第i件物品：dp[i][j] = dp[i − 1][j − w[i]] + v[i]

即状态转移方程为：

1
dp[i][j] = max(dp[i-1][j], j-w[i] >= 0 ? dp[i-1][j-w[i]]+v[i] : 0)

由状态方程可知，dp[i][j]的值只与dp[i-1][0,…,j-1]有关，所以可以采用滚动数组对空间优化。需要注意的是，为了防止上一层循环dp[0,…,j-1]被覆盖，需要逆向枚举j（空间优化前没有这个限制）。代码如下：

1
2
3
4
5
6
7
8
9
10
int solution01Knapsack(int N, int W, std::vector<int> &w, std::vector<int> &v) {
    // w[i]重量  v[i]价值
    std::vector<int> dp(W+1);
    for (auto i = 0; i < N; i++) {
        for (auto j = W; j >= w[i]; j--) {
            dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

时间复杂度为O(NW)，空间复杂度为O(W)。第i件物品装入或者不装入而获得的最大价值完全可以由前面i − 1件物品的最大价值决定，暴力枚举忽略了这个事实。

完全背包

设一共有N件物品，第i件物品的重量为w[i]，价值为v[i]，每件可以无限多个，最大总重量为W。

与01背包非常相似，状态dp定义一致，只是状态转移稍微不同：

  1. 不装入第i物品：dp[i][j] = dp[i − 1][j]（同01背包）
  2. 在能装入的前提下，因为每件物品有无限个，所以不从dp[i − 1][j − w[i]]转移，而是从dp[i][j − w[i]]转移，即装入第i种商品后还可以再继续装入该种商品。即装入第i件物品：dp[i][j] = dp[i][j − w[i]] + v[i]

状态转移方程为：

1
dp[i][j] = max(dp[i-1][j], j-w[i] >= 0 ? dp[i][j-w[i]]+v[i] : 0)

和01背包问题相似，也可以进行空间优化，不同点在于完全背包的j只能正向枚举而01背包只能逆向枚举，因为max第二项是dp[i]而01背包是dp[i-1]，即完全背包需要覆盖而01背包需要避免覆盖。代码如下：

1
2
3
4
5
6
7
8
9
10
int solutionUnboundedKnapsack(int N, int W, std::vector<int> &w, std::vector<int> &v) {
    // w[i]重量  v[i]价值
    std::vector<int> dp(W+1);
    for (auto i = 0; i < N; i++) {
        for (auto j = w[i]; j <= W; j++) {
            dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

完全背包问题也可以转化为01背包问题来解：将一种物品转换成最多能放下的若干件。

最简单的想法是，考虑到第i种物品最多装入W/w[i]件，于是把第i种物品转化为 W/w[i]件费用及价值不变的物品，然后求解这个01背包问题。时间复杂度为：$O(NW\frac{\sum{\frac{W}{w_i}}}{N}) = O(W\sum{\frac{W}{w_i}})$ 。

更高效的转化方法是采用二进制的思想：把第i种物品拆成重量为wi2k、价值为vi2k若干件物品，其中 k 取遍满足wi2k ≤ W的非负整数。这是因为不管最优策略选几件第i种物品，总可以表示成若干个刚才这些物品的和（例：13 = 20 + 22 + 23）。这样就将转换后的物品数目降成了对数级别。时间复杂度为：$O(NW\frac{\sum\log_2{\frac{W}{w_i}}}{N}) = O(W\sum\log_2{\frac{W}{w_i}})$。

多重背包

设一共有N件物品，第i件物品的重量为w[i]，价值为v[i]，数量限制为n[i]，最大总重量为W。

参考完全背包转为01背包的思想，k表示装入第i种物品的件数，k <= min(n[i],j/w[i])​

1
dp[i][j] = max{(dp[i-1][j-k*w[i]]+k*v[i]) for range(k)}

同理也可以进行空间优化，而且j也必须逆向枚举：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int solutionBoundedKnapsack(int N, int W,
                            std::vector<int> &w,
                            std::vector<int> &v,
                            std::vector<int> &n) {
    // w[i]重量  v[i]价值
    std::vector<int> dp(W + 1);
    for (auto i = 0; i < N; i++) {
        for (auto j = W; j >= w[i]; j--) {
            for (auto k = 1; k <= std::min(n[i], j / w[i]); k++) {
                dp[j] = std::max(dp[j], dp[j - k * w[i]] + k * v[i]);
            }
        }
    }
    return dp[W];
}

时间复杂度为：O(NWn̄) = O(W∑ni)，空间复杂度为：O(W)。

当然也可以采用二进制思路，将第i种物品分成了log2ni件物品，将时间复杂度优化为：O(W∑log2ni)。

杂项

背包问题还有一些其他变种问题。

恰好装满

要求：必须恰好装满背包。

只需要修改初始化，将dp[0, …, N][0]初始为0，其它dp值均初始化为-inf，因为此时只有容量为0的背包可以在什么也不装情况下被“恰好装满”，其它容量的背包初始均没有合法的解，应该被初始化为-inf。

总方案数

要求：求背包装满或则装至某一指定容量的总方案数。

修改转移方程中的max为sum。

二维背包

上文讨论的背包都只有一个限制：最大容量。二维背包指一个背包存在两个限制（比如重量和体积限制）。

此类问题的解法和一维背包相似，需要dp数组要多开一维，其他和一维背包一致。

输出最优方案

要求：输出背包问题的解方案。

可以参照一般动态规划的方案输出方法：记录每一个状态是由那条策略推导而出，以便回溯出上一个状态。

以01背包为例，再开辟一个数组P[i][j]来记录方案，P[i][j] = 0表示dp[i][j]采用第一种状态转移策略，即dp[i][j] = dp[i − 1][j]，P[i][j] = 1表示采用第二种状态转移策略，即dp[i][j] = dp[i − 1][j − w[i]] + v[i]，从而反推方案。

另外我们也可以从求出的dp数组进行反推，若 dp[i][j] = dp[i − 1][j] 说明未选第i个物品，反之说明选了。