背包问题详解

背包问题详解

01 背包问题

问题描述

有 n 个重量和价值分别为 \(w_i\)\(v_i\) 的物品。从这些物品中挑选出总重量不超过 W 的物品,求所有挑选方案中价值总和的最大值。

穷竭搜索

每个物品只有放和不放两种状态,则对每个物品是否放入背包进行搜索,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int rec(int i, int j) {
int res;
if (i == n) {
// 挑完了
res = 0;
} else if (j < w[i]) {
// 无法挑选
res = rec(i+1, j);
} else {
// 挑选和不挑选两种情况的最大值
res = max(rec(i+1, j), rec(i+1, j-w[i])+v[i]);
}
return res;
}

void solve() {
// 从第 0 个物品开始挑选,剩余重量为 W 的最大价值
printf("%d\n", rec(0, W));
}

这种方法搜索的深度是 n,每一层的搜索都需要两次分支,最坏的情况下需要 \(O(2^n)\) 的时间。

记忆化搜索

当然可以用记忆化搜索的方式,减少递归次数,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int dp[MAX_N+1][MAX_W+1];

int rec(int i, int j) {
if (dp[i][j] > 0) {
// 已经计算过,无需再次搜索,记忆化
return dp[i][j];
}
int res;
if (i == n) {
res = 0;
} else if (j < w[i]) {
res = rec(i+1, j);
} else {
res = max(rec(i+1, j), rec(i+1, j-w[i])+v[i]);
}
return dp[i][d] = res; // 返回并放入数组
}

void solve() {
memset(dp, -1, sizeof(dp));
printf("%d\n", rec(0, W));
}

在这种方法下,对于同样的参数,只会在第一次调用到时执行递归,参数的组合至多有 \(nW\) 种,所以只需要 \(O(nW)\) 的复杂度。

二维数组 dp

在记忆化搜索种,对于二维数组,每个参数只计算一次,则可以用二重循环的方式来计算 dp,无需递归根据 rec 的定义,定义 dp[i][j] 为从第 i 个物品开始挑选总重不超过 j 时,总价值的最大值。于是递推公式为:

\[dp[n][j] = 0 \\ dp[i][j] = \left \{\begin{aligned} & dp[i+1][j] & (j < w[i]) \\ & max(dp[i+1][j], dp[i+1][j-w[i]]+v[i]) & (其他)\end{aligned} \right.\]

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[MAX_N+1][MAX_W+1];

void solve() {
memset(dp, 0, sizeof(dp));
for (int i = n-1; i >= 0; --i)
for (int j = 0; j <= W; ++j) {
if (j < w[i])
dp[i][j] = dp[i+1][j];
else
dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]]+v[i]);
}
printf("%d\n", dp[0][W]);
}

这个方法复杂度与记忆化搜索相同,都是 \(O(nW)\)。当然,还有其他的递推式,如,定义 dp[i+1][j] 为从前 i 个物品种挑选总重不超过 j 时,总价值的最大值。则递推式为:

\[dp[0][j] = 0 \\ dp[i+1][j] = \left \{\begin{aligned} & dp[i][j] & (j < w[i]) \\ & max(dp[i][j], dp[i][j-w[i]]+v[i]) & (其他)\end{aligned} \right.\]

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[MAX_N+1][MAX_W+1];

void solve() {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; ++i)
for (int j = 0; j <= W; ++j) {
if (j < w[i])
dp[i+1][j] = dp[i][j];
else
dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i]);
}
printf("%d\n", dp[n][W]);
}

从状态转移的角度考虑,也可以从 dp[i][j] 向 dp[i+1][j] 和 dp[i+1][j+w[i]] 转移,(dp[i+1][j] 为从前 i 个物品种挑选总重不超过 j 时,总价值的最大值)则:

1
2
3
4
5
6
7
8
9
10
11
12
int dp[MAX_N+1][MAX_W+1];

void solve5() {
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= W; ++j) {
dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
if (j+w[i] <= W)
dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j]+v[i]);
}
printf("%d\n", dp[n][W]);
}

一维 dp

观察递推公式,

\[dp[0][j] = 0 \\ dp[i+1][j] = \left \{\begin{aligned} & dp[i][j] & (j < w[i]) \\ & max(dp[i][j], dp[i][j-w[i]]+v[i]) & (其他)\end{aligned} \right.\]

遍历 i+1 时,只用到了第 i 次遍历的值,且第 j 个只与上一轮第 j 个和第 j-w[i] 个有关。如果压缩 dp 成一维数组,且每次遍历,j 从大到小取,那么每次更新 d[j] 用到的 d[j] 和 d[j-w[i]]都是上一轮未更新的值,满足更新要求,完全可以压缩。写成代码为:

1
2
3
4
5
6
7
8
9
int dp[MAX_W+1];

void solve() {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; ++i)
for (int j = W; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
printf("%d\n", dp[W]);
}

第 i 次遍历代表着正在进行第 i 个物品的选择,则对每个物品的选择方法可进行封装,最后伪代码如下:

1
2
3
4
5
6
7
8
void ZeroOnePack(int weight, int value)
for (int j = W; j >= weight; --j)
dp[j] = max(dp[j], dp[j-weight]+value);

for (int i = 0; i < n; ++i)
ZeroOnePack(w[i], v[i]);

// dp[W]

当 W 过大时

题目不变,限制条件,当 \(1 \leq W \leq 10^9, 1 \leq w_i \leq 10^7, 1 \leq v_i \leq 100\) 时,此时 W 过大,此前秋节此问题的放大复杂度为 \(O(nW)\),对于这一问题的规模来说显然不够用。

现在可以试着改变 dp 的对象,之前我们用 dp 针对不同的重量限制计算最大的价值,这次不妨用 dp 针对不同价值计算最小的重量。

定义 dp[i+1][j] 为从前 i 个物品中挑选价值总和为 j 时总重量的最小值(不存在时就是一个充分大的数值 INF)。递推公式为:

\[dp[0][0]=0 \\ dp[0][j]=INF \\ dp[i+1][j]=min\{dp[i][j],dp[i][j-v[i]]+w[i] \}\]

最终的答案就对应于令 \(dp[n][j]\leq W\) 的最大的 j。复杂度为 \(O(n\sum_i v_i)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dp[MAX_N+1][MAX_N*MAX_V+1];

void solve() {
fill(dp[0], dp[0]+MAX_N*MAX_V+1, INF);
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= MAX_N*MAX_V; ++j) {
if (j < v[i])
dp[i+1][j] = dp[i][j];
else
dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i]);
}
}
int res = 0;
for (int i = 0; i <= MAX_N*MAX_V; ++i)
if (dp[n][i] <= W)
res = i;
printf("%d\n", res);
}

完全背包问题

问题描述

有 n 种重量和价值分别为 \(w_i\)\(v_i\) 的物品。从这些物品中挑选出总重量不超过 W 的物品,求所有挑选方案中价值总和的最大值,每种物品可以挑选任意多件。

拆分策略

其实就是选择物品 i 的时候,物品 i 有了多种选择情况,0,1,2,...,k,k*w[i] < j。那么第 i 种物品最多可以选择 W / w[i] 件,于是可以把第 i 种物品转化为 W / w[i] 个重量和价值均不变得物品,然后求解这个 01 背包问题。

当然拆解的时候,也可以采用高效的二进制思想,把第 i 种物品拆成重量为 \(w[i]* 2^k\)、价值为 \(w[i]*2^k\) 的若干件物品,其中 k 满足 \(w[i]*2^k \leq W\)。因为不管最优策略选几件第i种物品,总可以表示成若干个 \(2^k\) 件物品的和。(在多重背包使用)

三重循环

当然不转换为 01 背包,直接对每个物品选择 k 个的情况进行遍历,也是可以的,定义 dp[i+1][j] 为从前 i 个物品中挑选总重量不超过 j 的最大价值,递推关系为:

\[dp[0][j]=0 \\ dp[i+1][j]=max\{dp[i-k \times w[i]]+k\times v[i] | 0 \le k \}\]

1
2
3
4
5
6
7
8
9
10
11
int dp[MAX_N+1][MAX_W+1];

void solve() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= W; ++j) {
for (int k = 0; k * w[i] <= j; ++k)
dp[i+1][j] = max(dp[i+1][j], dp[i][j-k*w[i]]+k* v[i]);
}
}
printf("%d\n", dp[n][W]);
}

但是程序中具有三重循环,其复杂度为 \(O(nW^2)\)

二维 dp

可以知道,在计算 dp[i+1][j] 中选择 k 个的情况,与在计算 dp[i+1][j-w[i]] 种选择 k-1 个的情况是相同的。则可以更新递推关系为:

\[dp[0][j]=0 \\ dp[i+1][j]=max\{ dp[i][j],dp[i+1][j-w[i]]+v[i] \}\]

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[MAX_N+1][MAX_W+1];

void solve() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= W; ++j) {
if (j < w[i])
dp[i+1][j] = dp[i][j];
else
dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+v[i]);
}
}
printf("%d\n", dp[n][W]);
}

这样就可以在 \(O(nW)\) 时间内解决问题。

一维 dp

当然如 01 背包,这题也可以继续压缩空间复杂度,将二维 dp 压缩成一维。第 i 次第 j 列更新,需要用到的是 j 列本来的值,还有已经更新过的 j 列之前的值,所以这次遍历 j 从小到大顺序遍历即可。

1
2
3
4
5
6
7
8
9
int dp[MAX_W+1];

void solve() {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; ++i)
for (int j = w[i]; j <= W; ++j)
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
printf("%d\n", dp[W]);
}

同 01 背包问题,第 i 次遍历针对的是第 i 种物品,对每种物体选择的处理方式,则是顺序遍历,进行封装,得

1
2
3
4
5
6
7
8
void CompletePack(int weight, int value)
for (int j = w[i]; j <= W; ++j)
dp[j] = max(dp[j], dp[j-weight]+value);

for (int i = 0; i < n; ++i)
CompletePack(w[i], v[i]);

// dp[W]

多重背包问题

问题描述

有 n 种重量和价值分别为 \(w_i\)\(v_i\) 的物品。从这些物品中挑选出总重量不超过 W 的物品,求所有挑选方案中价值总和的最大值,每种物品至多选择 \(k_i\) 个。

拆分策略

直接将第 i 种物体,当作 \(k_i\) 个新的质量和价值不变的新物体,当作 01 背包问题来考虑。复杂度为 \(O(W*\sum k[i] )\)

考虑二进制思想,将复杂度降为 \(O(W*\sum log \ k[i])\)。假设第 i 种物品有 13 个,可以增加四个物品,其质量和价值分别是第 i 种物体的 1,2,4,6 倍。这四个数可以组合成 1... 13 中的任意一个数。即将第 i 种物品分成若干个物品,每个物品的系数分别为 \(1,2,4,...,2^{j-1},k[i]-2^j+1\),其中 j 是满足 \(2^{j}-1<k[i]\) 的最大整数。

这样在选择第 i 个物品的时候,就可以写成如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int dp[MAX_W+1];

void ZeroOnePack(int weight, int value)
for (int j = W; j >= weight; --j)
dp[j] = max(dp[j], dp[j-weight]+value);

void CompletePack(int weight, int value)
for (int j = weight; j <= W; ++j)
dp[j] = max(dp[j], dp[j-weight]+value);

void MultiPack(weight, value, amount) {
if (weight * amount >= W) {
CompletePack(weight, value);
return;
}
int j = 1;
while (j < amount) {
ZeroOnePack(j*weight, j*value);
amount -= j;
j *= 2;
}
ZeroOnePack(amount*weight, amount*value);
}

for (int i = 0; i < n; ++i)
MultiPack(w[i], v[i], k[i]);

// dp[W]

参考文献

  • 《挑战程序设计竞赛(第2版)》
  • https://www.kancloud.cn/kancloud/pack/70124
# DP

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×