背包问题-完全背包

例题

题目描述

此题和原题的不同点：

\(1\). 每种草药可以无限制地疯狂采摘。

\(2\). 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 \(t\) 和代表山洞里的草药的数目 \(m\)。

第 \(2\) 到第 \((m + 1)\) 行，每行两个整数，第 \((i + 1)\) 行的整数 \(a_i, b_i\) 分别表示采摘第 \(i\) 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

完全背包模型与 \(\text{0-1}\) 背包类似，与 \(\text{0-1}\) 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

我们可以借鉴 \(\text{0-1}\) 背包的思路，进行状态定义：设 \(dp_{i,j}\) 为只能选前 i 个物品时，容量为 j 的背包可以达到的最大价值。

需要注意的是，虽然定义与 \(\text{0-1}\) 背包类似，但是其状态转移方程与 \(\text{0-1}\) 背包并不相同。

思路

可以考虑一个最暴力的做法：对于第 \(i\) 件物品，枚举其选了多少个来转移。这样做的时间复杂度是 \(\text{O(n^3)}\) 的（肯定爆炸）。

状态转移方程如下：
\(dp_{i,j}=\max_{k=0} ^{+\infty }(dp_{i-1,j-k\times w_i}+v_i\times k)\)

考虑做一个简单的优化。可以发现，对于 \(dp_{i,j}\)，只要通过 \(dp_{i,j-w_i}\) 转移就可以了。因此状态转移方程为：

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

理由是当我们这样转移时，\(dp_{i,j-w_i}\) 已经由 \(dp_{i,j-2\times w_i}\) 更新过，那么 \(dp_{i,j-w_i}\) 就是充分考虑了第 \(i\) 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。

代码如下

#include <iostream>
using namespace std;
const int maxn = 1e4 + 5;
const int maxW = 1e7 + 5;
int n, W, w[maxn], v[maxn];
long long f[maxW];

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