跳转至

背包 DP

在学习本章前请确认你已经学习了动态规划部分简介

在具体讲何为 "背包 dp" 前,先来看如下的例题

[USACO07 DEC]Charm Bracelet

题意概要:有 n个物品和一个容量为 W的背包,每个物品有重量 w_{i}和价值 v_{i}两种属性,要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

在上述例题中,由于每个物体只有 2种可能的状态(取与不取),正如二进制中的 01,这类问题便被称为 “0-1 背包问题”。

0-1 背包

例题中已知条件有第 i个物品的重量 w_{i},价值 v_{i},以及背包的总容量 W

设 DP 状态 f_{i,W}为在只能放前 i个物品的情况下,容量为 W的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 i-1个物品的所有状态,那么对于第 i个物品,当其不放入背包时,背包的剩余容量不变,背包中物品的总价值也不变,故这种情况的最大价值为 f_{i-1,W};当其放入背包时,背包的剩余容量会减小 w_{i},背包中物品的总价值会增大 v_{i},故这种情况的最大价值为 f_{i-1,W-w_{i}}+v_{i}

由此可以得出状态转移方程:

f_{i,W}=\max(f_{i-1,W},f_{i-1,W-w_{i}}+v_{i})

在程序实现的时候,由于对当前状态有影响的只有 f_{i-1},故可以去掉第一维,直接用 dp_{W}来表示处理到当前物品 i时背包容量为 W的最大价值 f_{i,W}

还有一点需要注意的是,很容易写出这样的错误核心代码:

1
2
3
4
for (int i = 1; i <= W; i++)
  for (int l = 0; l <= W - i; l++)
    dp[l + w[i]] = max(dp[l] + v[i], dp[l + w[i]]);
    // 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]],f[i - 1][l] + w[i]),f[i][l + w[i]]); 简化而来

这段代码哪里错了呢?枚举顺序错了。

仔细观察代码可以发现:对于当前处理的物品 i和当前状态 f_{i,W},在 W\geqslant w_{i}时,f_{i,W}是会被 f_{i,W-w_{i}}所影响的。这就相当于物品 i可以多次被放入背包,与题意不符。(事实上,这正是完全背包问题的解法)

为了避免这种情况发生,我们可以改变枚举的顺序,从 W枚举到 w_{i},这样就不会出现上述的错误,因为 f_{i,W}总是在 f_{i,W-w_{i}}前被更新。

因此实际核心代码为

1
2
3
4
for (int i = 1; i <= W; i++)
  for (int l = W - i; l >= 0; l--)
    dp[l + i] = max(dp[l] + w[i], dp[l + i]);
    // 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]],f[i - 1][l] + w[i]),f[i][l + w[i]]); 简化而来
例题代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
const int maxn = 13010;
int n, v, w[maxn], v[maxn], dp[maxn];
int main() {
  std::cin >> n >> W;
  for (int i = 1; i <= n; i++)
    std::cin >> w[i] >> v[i];
  for (int i = 1; i <= n; i++)
    for (int l = W; l >= w[i]; l--)
      if (dp[l - w[i]] + v[i] > dp[l])
        dp[l] = dp[l - w[i]] + v[i];
  std::cout << dp[W];
  return 0;
}

完全背包

多重背包


评论