POJ1742 多重背包

典型的单调队列优化 dp。对于 $n$ 类物品，某类物品的数量为 $k$，价值为 $v$，容量为 $w$。那么考虑到这个种类的物品的时候有如下 dp 方程：

设 $dp[i]$ 表示容量为 $i$ 的时候得到的最大价值，那么我们就有：

$$dp[i]=\max\{dp[i-k \times w]+k \times v\}$$

换一种写法:

$$dp[mod+k \times w]=\max\{dp[mod+j \times w]+(k-j) \times v\}$$

这里为了方便，我们用 $s_j$ 表示 $dp[mod+j \times w]$，所以就有

$$dp[mod+k \times w]=\max\{s_j + (k-j) \times v\} = \max\{s_j-j \times v\}+k \times v$$

这里 $k$ 已经是定值，也就是说 $dp[mod+k \times w]$ 只和一定范围内的 $s_j-j \times v$ 的最大值有关，可以用单调队列优化。总的复杂度是 $O(N \times V)$ 的。

这道题比较简单，由于价值都是 1 的，我们就直接开一个 bool 型数组存储是否存在解就可以了。然后枚举到的 $k$ 如果 $dp[k]$ 是可达的，那么我们就将其 id 入队，否则就不管，另外由于价值一样，所以不要记录价值。

此类背包问题还可以进一步地优化，如果 $k$ 等于 $1$ 的时候直接写 0-1 背包，如果物品可以取得的总容量大于背包总容量，那么就直接写完全背包，因为这两种写法和单调队列相比常数小了非常多。

最后考虑到很大的输入输出量，选择 C++ 编译器。

完整代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 100010;

bool dp[MAX];
int id[MAX], c[120], v[120], f, b;

int main() {
  int n, m;
  freopen("in.txt", "r", stdin);
  while (scanf("%d%d", &n, &m), n || m) {
    for (int i = 1; i <= m; i++) dp[i] = false;
    dp[0] = true;
    for (int i = 0; i < n; i++) scanf("%d", &v[i]);
    for (int i = 0; i < n; i++) scanf("%d", &c[i]);
    for (int i = 0; i < n; i++) {
      int w = c[i] * v[i];
      if (c[i] == 1) {
        for (int j = m; j >= v[i]; j--) {
          if (dp[j - v[i]]) dp[j] = true;
        }
      } else if (w >= m) {
        for (int j = v[i]; j <= m; j++) {
          if (dp[j - v[i]]) dp[j] = true;
        }
      } else {
        for (int j = 0; j < v[i]; j++) {
          f = b = 0;
          for (int k = j; k <= m; k += v[i]) {
            if (f != b && k - id[f] > w) f++;
            if (dp[k]) {
              id[b++] = k;
            } else if (f != b) {
              dp[k] = true;
            }
          }
        }
      }
    }
    int ret = 0;
    for (int i = 1; i <= m; i++)
      if (dp[i]) ret++;
    printf("%d\n", ret);
  }
  return 0;
}