动态规划之背包问题

发表于 更新于 本文字数： 4k 阅读时长 ≈ 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(2^n)$，使用动态规划可以把时间复杂度控制在$O(N*W)$。求解的总目标是背包物品的总价值，变量有是否放入物品和书包限重。

定义$dp[i][j]$表示将前$i$件物品放入限重为$j$的书包可以获得的最大价值，其中$0 \leq i \leq N, \ 0 \leq j \leq \ 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$个物品，反之说明选了。