1. 朴素多重背包

现有 \(n\) 种物品, 已知第 \(i\) 种物品有 \(s_i\) 个, 每个的价值为 \(w_i\), 体积为 \(v_i\), 现有一个容积为 \(m\) 的背包, 问: 该背包能够装走的最大价值是多少

1.1 状态表示

设 \(f_{i, j}\) 表示关于前 \(i\) 种物品, 在占用空间 \(\leq j\) 的情况下, 对应的最大价值

1.2 状态转移方程

\(f_{i, j} = \max\limits_{k = 0}^{\min(\lfloor j \div v_i \rfloor, s_i)}(f_{i - 1, j - k \times v_i} + k \times w_i)\)
这里我们可能会联想到完全背包的状态转移方程, 并使用: \(f_{i, j} = \max(f_{i - 1, j}, f_{i, j - v_i} + w_i)\)

然而这是不对的: 我们假设第 \(s_i = 2\), 且 \(j \geq 3 \times v_i\)
\(f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - v} + w, f_{i - 1, j - 2 \times v} + 2 \times w)\)
\(f_{i, j - v} = \max(f_{i - 1, j - v}, f_{i - 1, j - 2 \times v} + w, f_{i - 1, j - 3 \times v} + 2 \times w)\)

此时, 当我们使用了完全背包的那个状态转移方程的话, 岂不是第 \(i\) 种物品凭空多出了一个? 这必定是错误的, 故此, 我们只能使用时间复杂度较大的那个状态转移方程

1.3 代码实现

for (int i = 1; i <= n; ++ i)
  for (int j = m; j >= 0; -- j)
    for (int k = 0; k <= s[i] && k * v[i] <= j; ++ k)
      f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);

cout << f[m] << endl; // f[m] 表示前 n 种物品, 在总体积不超过 m 的情况下的最大价值

2. 二进制优化多重背包

对于任意一个整数, 我们都可以使用二进制的形式来表示

因此, 我们可以将 \(s_i\) 个价值为 \(w_i\), 体积为 \(v_i\) 的物品转换成 \(log_2s_i + 1\) 个物品的集合, 价值和体积分别为 \(k \times w_i\), \(k \times v_i\) \((k \in \{2^0, 2^1,\;..., 2^{log_2s_i - 1}, s_i - (2^{log_2s_i} - 1)\})\)

以 \(s_i = 666\) 举例: 可以划分为 \(log_2666 + 1 = 10\) 个物品的集合, \(\{1, 2, 4, 8, 16, 32, 64, 128, 256, 666 - (2^9 - 1) = 155\}\)
以 \(s_i = 256\) 举例: 可以划分为 \(log_2256 + 1 = 9\) 个物品的集合, \(\{1, 2, 4, 8, 16, 32, 64, 128, 256 - (2^8 - 1) = 1\}\)
以 \(s_i = 511\) 举例: 可以划分为 \(log_2511 + 1 = 9\) 个物品的集合, \(\{1, 2, 4, 8, 16, 32, 64, 128, 511 - (2^8 - 1) = 256\}\)

我们对这些物品集合使用01背包的解决方案, 时间复杂度为 \(O(m\sum\limits_{i = 1}^{n}log_2s_i)\)

2.1 代码实现

int f[N];
int v[N], w[N]; // v[i] 表示第 i 个物品集合的体积
int cnt = 0; // cnt 记录了当前物品集合的数量

// 二进制优化
for (int i = 1; i <= n; ++ i) {
  int vi, wi, si; // 第 i 类物品的体积, 价值, 数量
  cin >> vi >> wi >> si;

  for (int k = 1; si >= k; k <<= 1) {
    v[cnt] = k * vi;
    w[cnt ++] = k * wi;
    si -= k;
  }

  if (si) {
    v[cnt] = vi * si;
    w[cnt ++] = wi * si;
  }
}

// 01 背包
for (int i = 0; i < cnt; ++ i) 
  for (int j = m; j >= v[i]; -- j)
    f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

3. 单调队列优化多重背包

对于状态转移方程: \(f_{i, j} = \max\limits_{k = 0}^{\min(\lfloor j \div v_i \rfloor, s_i)}(f_{i - 1, j - k \times v_i} + k \times w_i)\)
如果使用单调队列来维护 \(\{f_{i - 1, j}, f_{i - 1, j - v} + w, f_{i - 1, j - 2 \times v} + 2 \times w, \;...\}\), 即可以 \(O(1)\) 的时间获取 \(f_{i, j}\) 的值, 优于没有优化的 \(O(s_i)\)
对于 \(n\) 种物品, \(m\) 种体积, 时间复杂度为 \(O(nm)\)

3.1 代码实现

int f[N], g[N], q[M];

for (int i = 1; i <= n; ++ i) {
  int v, w, s;
  cin >> v >> w >> s;

  // 对 f[i][j] 的更新需要用到 f[i - 1][j - k * v]
  // 故用 g 来代替 f[i - 1]
  memcpy(g, f, sizeof(f));

  // 从体积为 0, 1, 2, 3, ..., v - 1 开始更新
  for (int j = 0; j < v; ++ j) {
    int h = 0, t = -1;
    
    for (int k = j; k <= m; k += v) {
      // 若队头元素所对应的体积即使加上所有该类物品也无法达到 k, 则出队
      while (h <= t && q[h] < k - s * v) ++ h;

      // 保证单调队列是从小到大排列的
      // (k - q[t]) / v 表示从体积 q[t] 到体积 k 还可以放下的该类物品的数量
      while (h <= t && g[k] >= g[q[t]] + (k - q[t]) / v * w) -- t;
      q[++ t] = k; // 入队

      f[k] = g[q[h]] + (k - q[h]) / v * w;
    }
  }
}

cout << f[m] << endl;

4. 例题

#include 
#include 

using namespace std;

const int N = 1e4 + 10;
const int M = 1e3 + 10;

int f[M]; // 01/unbounded knapsack
int q[M], g[N]; // multiple knapsack

int main() {
  int h1, m1, h2, m2;
  int n, m, v, w, s;

  scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &n);

  m = (h2 - h1) * 60 + m2 - m1;

  for (int i = 1; i <= n; ++ i) {
    scanf("%d%d%d", &v, &w, &s);

    if (s > 1) { // multiple kp
      memcpy(g, f, sizeof(f));

      for (int j = 0; j < v; ++ j) {
        int h = 0, t = -1;
        for (int k = j; k <= m; k += v) {
          while (h <= t && q[h] < k - s * v) ++ h;

          while (h <= t && g[q[t]] + (k - q[t]) / v * w <= g[k]) -- t;
          q[++ t] = k;

          f[k] = g[q[h]] + (k - q[h]) / v * w;
        }
      }
    } else if (s == 1) { // 01 kp
      for (int j = m; j >= v; -- j)
        f[j] = max(f[j], f[j - v] + w);
    } else { // unbounded kp
      for (int j = v; j <= m; ++ j)
        f[j] = max(f[j], f[j - v] + w);
    }
  }
  
  printf("%d", f[m]);
  return 0;
}