背包问题-01背包

首先我们要明白什么是01背包，在下述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的 \(0\) 和 \(1\)，这类问题便被称为\(\text{「0-1 背包问题」}\)。

题目描述

有 \(N\) 件物品和一个容量为 \(M\) 的背包。第 \(i\) 件物品的重量是 \(W_i\)，价值是 \(D_i\)。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

第一行：物品个数 \(N\) 和背包大小 \(M\)。

第二行至第 \(N+1\) 行：第 \(i\) 个物品的重量 \(W_i\) 和价值 \(D_i\)。

输出格式

输出一行最大价值。

我们可以设状态\(dp_{i,j}\)为在能放前\(n\)个的前提下，容量为\(j\)的背包所能达到的最大值。
我们在对于第\(i\)个物品时，有以下两个选则：

• \(dp_{i_j}=dp_{i_j-1}\) (不取)
• \(dp_{i_j}=dp_{i_j}-w_i+d_i\) (取)

综合一下便是\(dp_{i_j}=\)\(\max\)\((dp_{i_j-1},dp_{i_j}-w_i+d_i)\)

这里如果直接采用二维数组对状态进行记录，会出现 MLE。可以考虑改用滚动数组的形式来优化。

因为对\(dp_i\)影响的只有\(dp_{i-1}\),可以去掉第一维，直接用 \(dp_{i}\) 来表示处理到当前物品时背包容量为 \(i\) 的最大价值，得出以下方程：

• \(dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-w_{i}}+v_i)\)

综上所述

#include <iostream>
using namespace std;
const int maxn = 13010;
int n, W, w[maxn], v[maxn], f[maxn];

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];  // 读入数据
  for (int i = 1; i <= n; i++)
    for (int l = W; l >= w[i]; l--)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // 状态方程
  cout << f[W];
  return 0;
}