跳转至

背包 DP

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

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

例题 [USACO07DEC] 手链 Charm Bracelet

本题题意可概括为——N 物体,放入容量为 M 的背包,要求使总价值最大。由于每个物体只有 2 种情况——取与不取,正如二进制中的 0 和 1——这类问题便被称为 “0-1 背包问题”。

0-1 背包

例题中已知条件有第 i 个物体的体积 v[i] 和价值 w[i], 背包总容量

显而易见的是,可以计算总价值的,只有已经放入背包的物体,因此该题中对 "是否为最大值" 的判断是建立在 "已经放入背包之中" 的基础之上的

已知对于一个容量为 v1,可以放置第 1 到第 i 件物体的背包,其最大总价值很明显等于容量为 v1 的背包,放有第 1 到第 (i-1) 件物体时的最大值 (第 i 件物体不取时) 或者是容量为 v1-v[i]的背包,放有第 1 到第 (i-1) 件物体时的最大值 + wi

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

  • dp[v1][i]=max(dp[v1][i-1],dp[v1-v[i]][i-1]+w[i])

有了这样的思路,就可以顺利地写出代码了

1
2
for (int i = 1; i <= v1; i++)
  for (int l = 0; l <= v1 - i; l++) dp[l + i] = max(dp[l] + w[i], dp[l + i]);

按照正确的思路,写出了这样的核心代码,然后就可以提交......

错!

让我们再回头看一下代码,i 表示当前判断的是第 i 个物体,l 则穷举体积,可是注意一个地方——l 是从 0 到 v1-v[i]

这意味着什么呢?举个栗子,可能在体积为 (l) 处取物体 i 新的 dp 值存到体积为 (l+v[i]) 处, 而在体积为 (l+v[i]) 处,物体 i 再次被取

所以,当以 0~v1-v[i]的顺序穷举时,物体实际上可能被加入多遍,这显然与题意不符

因此为了避免多取,穷举顺序应为 v1-v[i]~0

因此实际核心代码为

1
2
for (int i = 1; i <= v1; i++)
  for (int l = v1 - i; l >= 0; l--) dp[l + i] = max(dp[l] + w[i], dp[l + i]);

例题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int maxn = 13010;
int n, v, c[maxn], w[maxn], most[maxn];
int main() {
  cin >> n >> v;
  for (int i = 1; i <= n; i++) {
    cin >> c[i] >> w[i];
  }
  for (int i = 1; i <= n; i++)
    for (int l = v; l >= c[i]; l--) {
      if (most[l - c[i]] + w[i] > most[l]) most[l] = most[l - c[i]] + w[i];
    }
  cout << most[v];
  return 0;
}

Ps. 事实上,由小到大穷举是另一种背包问题的解法,稍后会提到

完全背包

多重背包


评论