动态规划之背包问题

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

动态规划之背包问题

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

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

定义

我们有\(n\)种物品，物品\(i\)的重量为\(w_i\)，价值为\(v_i\)

我们假定所有物品的重量和价值都是非负数，背包所能承受的最大重量为\(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\)最多只能选择\(b_i\)个，则问题称为多重背包问题（有界背包问题）。

    可以用公式表示为： \[ \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(n^2)\)，使用动态规划可以把时间复杂度控制在\(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\)种物品拆成重量为\(w_i 2^k\)、价值为\(v_i 2^k\)若干件物品，其中 k 取遍满足\(w_i 2^k \leq W\)的非负整数。这是因为不管最优策略选几件第\(i\)种物品，总可以表示成若干个刚才这些物品的和（例：\(13 = 2^0 + 2^2 + 2^3\)）。这样就将转换后的物品数目降成了对数级别。时间复杂度为：\(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(NW\bar n) = O(W\sum{n_i})\)，空间复杂度为：\(O(W)\)。

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

杂项

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

恰好装满

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

只需要修改初始化，将\(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\)个物品，反之说明选了。