首先对符号作一些规定：
n：物品种类数
W：背包容量
w[i]：第i种物品的重量
v[i]：第i种物品的价值
c[i]：第i种物品的数量
f[i]：使用i重量所能获得的最大价值
01背包问题
约定：for any i, c[i] = 1
for (int i = 1; i <= n; ++i)
for (int j = W; j >= w[i]; --j)
f[j] = max(f[j], f[j - w[i]] + v[i]);
完全背包问题
约定：for any i, c[i] = inf
for (int i = 1; i <= n; ++i)
for (int j = w[i]; j <= w; ++j)
f[j] = max(f[j], f[j - w[i]] + v[i]);
多重背包问题
-
方法一：暴力拆。太暴力了，也就对拍用，略。
-
方法二：二进制拆。c[i] = 1 + 2 + 4 + ... + 2^p + rest。由此可表示出所有可能。偷懒时可用。代码略。
-
方法三：单调队列优化DP。
这个是重点。
观察转移特点:
f[i] = max{f[i - w] + v, f[i - 2 * w] + 2 * v,
f[i - 3 * w] + 3 * v... f[i - c * w] + c * v}
对于f[i + v]来说：
f[i + v] = max(f[i] + v, f[i - w] + 2 * v...
f[i - (c - 1) * w] + (c - 1) * v}
发现它是个窗口长度为c的滑动窗口问题。因此，在与v同余的j（重量）间，我们可以用单调队列转移。
值得注意的是，每个f要从之前的f转移，即要开一个oldf记录考虑该物品前的f数组。还有，注意到滑动窗口中的每个f所加的v的个数不同，但要加就一块加一个v，相对大小不变；f[i]的i越大，加的越少，因此转化成减即可。
代码如下：
for (register int i = 1; i <= n; ++i) {
read(w); read(v); read(c);
memcpy(oldf, f, sizeof(f));
for (register int r = 0; r < w; ++r) {//ÓàÊý
front = rear = 0;
for (register int j = r; j <= W; j += w) {
f[j] = oldf[j];
if (front < rear && (j - q[front + 1]) / w > c) front++;//²»ÄÜÓÉ´óÓÚk¸öiתÒÆÀ´
if (front < rear)
f[j] = max(f[j], oldf[q[front + 1]] + (j - q[front + 1]) / w * v);
while (front < rear && oldf[q[rear]] - (q[rear] - r) / w * v < oldf[j] - (j - r) / w * v)
rear--;
q[++rear] = j;
}
}
}
- 方法四：前缀和优化（这个在背包计数问题中有很大的优势）
发现能转移到 (f(x)) 的都是模 (w_x) 相同的数中的一段区间，于是可以直接用前缀和优化：
inline void work() {
f[0][0] = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= m; ++j) {
if (j - w[i] >= 0) sum[j] = (sum[j - w[i]] + f[i - 1][j]) % P;
else sum[j] = f[i - 1][j];
}
for (int j = 0; j <= m; ++j) {
if (j - (K+1) * w[i] < 0) f[i][j] = sum[j];
else f[i][j] = (sum[j] - sum[j - (K+1) * w[i]] + P) % P;
}
}
}
分组背包问题
奇怪的背包问题
w[i]极大
w[i]、v[i]都大，但w[i] = a * 2^b
dfn 优化树形背包
树形背包，如果选 (x) 就必须选 (x) 的所有祖先。(n le 500,m le 4000)
有个显然的 (nm^2) 暴力，直接树形DP，对于儿子暴力合并即可。
我们还可以把 dfn 搞出来，设 (f_i) 表示考虑完 (i...n) 以后的背包数组。这样的话，如果 (x) 不选，那其子树必须不选，于是直接继承子树后面的背包数组即可。如果选，那么可以从 (dfn_x+1) 处转移过来。这样，每次只涉及到背包中加一个物品，复杂度是 (O(nm)) 的。