本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 12:46:56

对于原问题，这就是一个简单的计数 DP。设 $f(i)$ 是将这些物品放进体积为 $i$ 的背包内的方法数量，则转移方程是

$$ f(i) = \begin{cases} 0 & i = -1 \ 1 & i = 0 \ \sum\limits_{j = 0}^{n} f(i - \min (w_j, i + 1)) & \text{otherwise} \end{cases} $$

写成代码便是

rep (i, 0, n) rrep (j, v, w[i]) dp[j] += dp[j - w[i]];

对于本问题，我们要求的是删除某个物品 $i$ 后的最大容积。

明显我们有以下等式：

$$ f(n) = f(n - w_0) + f(n - w_1) + \cdots f (n - w_{i}) + \cdots + f(n - w_k) $$

删除物品 $i$ 后的 $f(n)$ 应当减去 $f(n - w_i)$。于是，我们可以计算出去除了 $i$ 后的 tp：

rep (i, 0, n) rep (j, 0, v + 1)
  if (j < w[i]) tp[j] = dp[j];
  else tp[j] = dp[j] - dp[j - w[i]];

这个复杂度是 $O(nV)$ 的，显然能够通过。

编码时注意取模即可。