背包类型动态规划¶

背包类型动态规划是一种在各大竞赛、考场中经常出现的一类动态规划问题。背包类型动态规划十分灵活，但是只要掌握了诀窍，任何题目不管怎样变化都十分简单。

无价值背包¶

这种题目的物品都是没有价值的，可以使用 \(0/1\) 来标记可否到达的状态。

拼数

给你 \(n\) 个正整数数，问你能否在其中选择若干个数，使得选择的数的和正好为 \(m\)。

暴力思想¶

还是一眼想到了之前的搜索，我们用搜索函数 \(f(x,k)\) 表示当前正在选择第 \(x\) 个数，前面的数累加起来已经达到了 \(k\)，那么对于 \(a_x\)，可以选择或者不选择，往后搜就行了。

加个剪枝：如果在搜索过程中 \(k\) 已经大于 \(m\) 了，由于 \(a_i\) 都是正整数，再搜下去已经没有了意义，我们就直接退出搜索函数。如果此时 \(x=n+1\) 并且 \(k=m\)，就代表了我们已经搜出了解。

暴搜代码

void dfs(int x, int k) {
  if (x > n) {
    return ans |= k == m, void();
  }
  if (k > m) {
    return;
  }
  dfs(x + 1, k + a[x]);
  dfs(x + 1, k);
}

dp 思想¶

我们之前也学习了简单的 dp 题，那么我们能否想出这道题目如何用 dp 做呢？在搜索过程中，我们发现，\(x\) 和 \(k\) 有可能多次相同，也就是说其实我们只需要记录使用前 \(x\) 个数能否到达 \(k\) 就行了。

设 \(f(i,j)\) 表示为使用前 \(i\) 个数，能否到达 \(j\)，那么对于任意的数，跟搜索一样需要对选不选择做决策。不选，\(j\) 还是 \(j\)，直接让 \(f(i,j)\) 等于 \(f(i-1,j)\) 就行了。如果要选，那么 \(j\) 就要减去没选时与现在的差，也就是 \(j-a_x\)，那么 \(f(i,j)=f(i-1,j-a_x)\)。同理，取最大值即可。

注意，dp 前需要设好边界。这题在选 \(0\) 个数的情况下，和为 \(0\)，那么 \(f(0,0)=1\)。

dp 思想

dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    dp[i][j] = max(dp[i - 1][j], j >= a[i] ? dp[i - 1][j - a[i]] : 0);
  }
}

dp 的优化¶

滚动数组优化¶

在前面的 dp 当中，dp 数组是一个 \(n\times m\) 的二维数组，当 \(n\) 或 \(m\) 很大是，空间就会承受不住，所以我们需要进行空间优化。通过阅读状态转移方程我们可以的值，其实 \(dp_i\) 这一层的状态只会由 \(dp_{(i-1)}\) 得到，那么我们就可以将 \(dp_{(i-1)}\) 单独压成一个数组，然后不断进行滚动。具体可以参照下面的代码。

滚动数组优化

f[0] = 1;
for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    f[j] = dp[j] = max(f[j], j >= a[i] ? f[j - a[i]] : 0);  
    // 由于 j 只会访问 < j 的元素，因此可以变转移边滚动 
  }
}

压数组¶

如果你觉得滚动数组还不够的话，可以尝试压数组。观察转移方程，可以发现 \(j\) 只会访问 \(\le j\) 的元素，因此我们直接倒序枚举 \(j\)，那么 \(j-a_i\) 就一定是上一层状态了。

压数组

for (int i = 1; i <= n; i++) {
  for (int j = m; j >= a[i]; j--) {
    dp[j] |= dp[j - a[i]];
  }
}

注意

压数组有一定局限性，而滚动数组是只要只访问了上一层的状态就可以使用。

01 背包¶

01 背包是一种每一个物品只能选择一次的背包问题，其实我们刚才的拼数问题就是一个 01 背包，只不过没有价值而已。而在 01 背包当中，大部分都是需要求最大或是最小价值的。别担心，引入了价值之后题目也会非常简单。

01 背包问题

给出 \(n\) 个物品，第 \(i\) 个物品需要花费 \(w_i\) 的钱，但是可以获得 \(v_i\) 的价值。现在你带了 \(m\) 元，问你在使用不超过 \(m\) 元的情况下，最多可以获得多少的价值。

十分简单，还是设 \(f(i,j)\) 表示为选择了前 \(i\) 个物品，使用了 \(j\) 的钱，但是附带属性从原来的“是否能够满足”变成了“最大价值”。也非常简单，每一个物品都有选或不选的决策，如果不选，那么答案很显然就是 \(f(i-1,j)\)；如果选，那么使用的钱数就变更为没有选当前物品的钱数，也就是 \(j-w_i\)，然后将价值加上 \(v_i\)，取最大值即可。也就是 \(f(i,j)=\max(f(i-1,j),f(i-1,j-w_i)+v_i)\)。

很显然，由于遍历 \(j\) 时只会访问上一层状态 \(\le j\) 的部分，那么我们同样可以使用“压数组”的方法对 dp 的空间进行优化。

注意

在代码中，我们并没有设定边界状态和初始化 dp 数组，这是因为题目中并不需要完全花完 \(m\) 元，也就意味着我们可以“浪费”一些钱。而浪费 \(j\) 元，\(f(j)\) 就等于 \(0\)，因此不用去可以设定初始状态，但是在其他的题目中一定要仔细审题，看清楚到底要不要设置初始状态。

01 背包代码

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    dp[i][j] = max(dp[i - 1][j], j >= w[i] ? dp[i - 1][j - w[i]] + v[i] : 0);
  }
}

加入压数组优化

for (int i = 1; i <= n; i++) {
  for (int j = m; j >= w[i]; j--) {
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  }
}

完全背包¶

完全背包，就是每一个物品可以选择无线次，其他信息没有变。

由于每一个物品可以选择无限次，那么我们不仅需要遍历上一层的状态，还需要遍历当前层的状态。不过，在压数组的时候，为了避免重复选择，我们就让 \(j\) 倒序枚举，而这里正好可以取无限次，那么我们就可以利用这个小特性进行操作。

这个特性的原理是保存了当前层状态和上一层状态的最优值，那么遍历时就可以同时从上一层和当前层进行转移。很明显，由于它们两个状态都是一样的 \(j\)，那么只需要保留最大值就行了。

代码

for (int i = 1; i <= n; i++) {
  for (int j = w[i]; j <= m; j++) {
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  }
}

多重背包¶

多重背包问题

有 \(n\) 个物品，第 \(i\) 件物品需要 \(w_i\) 元，可以获得 \(v_i\) 的价值，但是只有 \(c_i\) 的数量。问你在花不超过 \(m\) 元的前提条件下最多可以获得多少的价值。

暴力拆分法¶

对于每一个物品，直接看做 \(c_i\) 个只能选一次的物品，然后暴力 01 背包就行了。时间复杂度 \(\mathcal O(nm\sum\limits_{i=1}^{n}{c_i})\)。

代码

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= c[i]; j++) {
    for (int k = m; k >= w[i]; k--) {
      dp[k] = max(dp[k], dp[k - w[i]] + v[i]);
    }
  }
}

二进制拆分¶

对于拆分的题目，我们很容易想到二进制。对于一个数 \(x\)，我们可以使用 \(\log_2 x\) 个二的 \(n\) 次幂的数来拼凑出 \(x\)，因此我们就对 \(c_i\) 进行拆分，将一件物品拆分成 \(\log_2 c_i\) 件小物品。时间复杂度 \(\mathcal O(nm\sum\limits_{i=1}^{n}\log_2 c_i)\)。

注意拆分完后面的余数需要进行特殊处理，我这里使用了取最小值来进行处理。

代码

for (int i = 1; i <= n; i++) {
  for (int j = 1; c[i]; c[i] = max(0, c[i] - j), j <<= 1) {
    for (int k = m; k >= w[i] * min(j, c[i]); k--) {
      dp[k] = max(dp[k], dp[k - w[i] * min(j, c[i])] + v[i] * min(j - c[i]));
    }
  }
}

单调队列优化¶

我们知道，如果是正向转移的话，那么 \(dp_j\) 就可以转移到 \(dp_{(j+k\times w_i)}\)，那么我们就枚举 \(j\)，然后枚举 \(k\)，接着使用一个单调队列存储可用的最大值，然后进行转移。我们这里限制了单调队列的转移长度 \(\min(\lfloor\cfrac{m}{w_i}\rfloor,c_i)\)，超出就退出。由于第二三重循环正好枚举了 \(m\) 次，因此这种方法的实现复杂度是 \(\mathcal O(nm)\) 的，十分优秀。

不过这种算法已经超出了 NOIp 的范围了，而且很难理解，因此在实际使用中往往会使用二进制拆分。

代码

for (int i = 1; i <= n; i++) {  // 枚举 n 个数
  c[i] = min(m / w[i], c[i]);   // 计算极限值，超出了无意义
  for (int j = 1; j <= w[i]; j++) {              // 枚举偏移
    q.clear();                                   // 清空队列
    for (int k = 0; k <= (m - j) / w[i]; k++) {  // 枚举选择 k 个
      int x = dp[k * c[i] + j] - k * v[i];       // 计算答案
      for (; q.size() && q.front().first < k - c[i]; q.pop_front()) { }  // 将队头无用的去掉
      for (; q.size() && q.back().second <= x; q.pop_back()) { }         // 将队尾更劣的去掉
      q.emplace_back(k, x);                                              // 入队
      dp[k * c[i] + j] = q.front().second + k * v[i];                    // 取最优的答案转移
    }
  }
}

这就是背包类型动态规划的几类经典问题，虽然在竞赛中形式多变，但基本上都是换汤不换药，只要掌握解题的方法就可以迎刃而解。