动态规划之背包问题

动态规划之背包问题

背包问题(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\)个物品,反之说明选了。