背包 DP

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

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

本题题意可概括为——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]);

例题代码

#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. 事实上，由小到大穷举是另一种背包问题的解法，稍后会提到

完全背包¶

多重背包¶

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

背包 DP

0-1 背包¶

完全背包¶

多重背包¶

评论