32 · 背包问题：0/1 与完全背包

背包是 DP 里最像“套路”的一类：有 n 件物品，每件有体积 w 和价值 v，背包容量 V，在总体积不超过 V 的前提下让总价值最大。P1048 采药就是它：T = 1000 的时间当容量，M = 100 株草药当物品。

0/1 背包和完全背包的代码只差一个不等号的方向，但差的方向后面是两件完全不同的事：dp[j] 被这一层更新之后，还允不允许这一层再拿它去更新别人。把这句话想通，背包就没有难点了。

• 0/1 背包：每件物品只能取 0 次或 1 次。内层容量倒序。
• 完全背包：每件物品可以取任意多次。内层容量正序。
• 多重背包：第 i 件物品最多取 c_i 次。把 c_i 二进制拆成若干组，转成 0/1 背包。
• 方案计数：把 max 换成加法，dp 的含义从“最大价值”变成“方案数”。

// 二维写法：想清楚用这个
for (int i = 1; i <= M; ++i)
    for (int j = 0; j <= T; ++j) {
        dp2[i][j] = dp2[i - 1][j];                                  // 不选第 i 件
        if (j >= t[i])
            dp2[i][j] = max(dp2[i][j], dp2[i - 1][j - t[i]] + v[i]); // 选第 i 件，从上一层转移
    }

// 一维写法：提交用这个
for (int i = 1; i <= M; ++i)
    for (int j = T; j >= t[i]; --j)                                 // 倒序！
        dp[j] = max(dp[j], dp[j - t[i]] + v[i]);

// 0/1 背包：每件最多一次
for (int i = 1; i <= M; ++i)
    for (int j = T; j >= t[i]; --j)
        dp[j] = max(dp[j], dp[j - t[i]] + v[i]);

// 完全背包：每件无限次
for (int i = 1; i <= M; ++i)
    for (int j = t[i]; j <= T; ++j)
        dp[j] = max(dp[j], dp[j - t[i]] + v[i]);

const int NEG = -0x3f3f3f3f;

// 恰好装满的 0/1 背包
dp[0] = 0;                                  // 唯一合法的起点
for (int j = 1; j <= V; ++j) dp[j] = NEG;    // 其余一律“不可达”

for (int i = 1; i <= n; ++i)
    for (int j = V; j >= w[i]; --j)
        if (dp[j - w[i]] != NEG)             // 不可达的来源不许参与转移
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

if (dp[V] < 0) cout << "impossible\n";       // 用 < 0 判，不要用 == NEG
else           cout << dp[V] << "\n";

#include <bits/stdc++.h>
using namespace std;

const int MAXT = 1005, MAXM = 105;
int t[MAXM], v[MAXM];          // t：采这株草药要花的时间；v：它的价值
int dp[MAXT];                  // dp[j]：时间上限为 j 时能采到的最大价值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, M;
    cin >> T >> M;
    for (int i = 1; i <= M; ++i) cin >> t[i] >> v[i];

    // 物品在外层、容量在内层：这是 0/1 背包唯一正确的嵌套顺序
    for (int i = 1; i <= M; ++i)
        for (int j = T; j >= t[i]; --j)                 // 倒序：j-t[i] 还是上一层，草药只采一次
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);

    cout << dp[T] << "\n";                              // 容量 T 时的最优值就是答案
    return 0;
}

把“为什么倒序”钉死。设只有一件物品：w = 2、v = 3、V = 6，dp 全 0。看两种方向跑出来的表。

正序时 j = 4 读到的 dp[2] 已经是 3（本轮刚算出来的），于是 3 + 3 = 6——同一件物品被用了两次。倒序时 j = 4 读到的 dp[2] 还是 0，只能得 3。

一句话总结：一维数组同时扮演“上一层”和“本层”两个角色，方向决定你读到的是哪一个。倒序读到旧层（0/1），正序读到新层（完全背包）。

所以完全背包不需要新写法，只要把方向反过来：正序时 dp[j−w] 刚被本层更新过，允许“在这件物品已经用过的基础上再用一次”，正好等于无限件。

// 完全背包：每件物品可以取任意多次
for (int i = 1; i <= M; ++i)
    for (int j = t[i]; j <= T; ++j)          // 正序：允许接着用这件物品
        dp[j] = max(dp[j], dp[j - t[i]] + v[i]);

模板题是 P1616 疯狂的采药：每株草药可以无限采，其余读入格式与 P1048 一模一样，改动只有内层方向一处。它的 T 比 P1048 大得多，所以还要多算一步账：dp 数组的内存 = T × 4 字节。T = 10⁷ 时就是 40 MB，开两个数组直接 MLE。

另外注意：完全背包的 dp 初值仍然全填 0。因为“一件都不取、容量随便剩多少”本身就是合法的 0 价值方案，不需要 −INF 那一套。

恰好装满是背包的第二种语义：不是“不超过 V”，而是“必须正好凑到 V”。状态转移一字不改，改的是初值。

为什么初值能改变语义：dp[j] 的值来自“从某个更小的 j 转移过来”，一路追溯下去终点一定是 dp[0]。如果 dp[0] = 0 而其余全填 −INF，那么只有“真能由若干件物品体积相加得到 j”的状态才会被更新成非负值，其余全是 −INF。最后 dp[V] 若仍小于 0，说明凑不出来。

const int NEG = -0x3f3f3f3f;
int dp[MAXT];

dp[0] = 0;                                  // 容量 0 天然装满，价值 0
for (int j = 1; j <= V; ++j) dp[j] = NEG;    // 其余容量都是“还没做到”

for (int i = 1; i <= n; ++i)
    for (int j = V; j >= w[i]; --j)          // 0/1：倒序
        if (dp[j - w[i]] != NEG)             // 来源不可达就不能转移
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

if (dp[V] < 0) cout << "impossible\n";       // 装不满
else           cout << dp[V] << "\n";

方案计数是第三种语义：把 max 换成加法，dp 的含义从“最优值”变成“方案数”。此时初值又变了：dp[0] = 1，其余 0。

dp[0] = 1 的理由：什么都不选、恰好用掉 0 的容量，这也算一种方案。写 0 的话，所有加法都会乘上 0，整张表恒等于 0。这和“恰好装满写 −INF”是同一件事的两面——不可达的状态必须贡献 0（加法）或者被排除（取 max）。

// 0/1 方案计数：n 个数里选若干，使和恰好等于 m，问方案数
long long dp[10005];
dp[0] = 1;                                  // 和为 0 的方案：一个都不选

for (int i = 1; i <= n; ++i)
    for (int j = m; j >= a[i]; --j)          // 倒序：每个数只能用一次
        dp[j] += dp[j - a[i]];               // 加法原理：不合这个数 + 合这个数

cout << dp[m] << "\n";

// 第 i 种物品：体积 w、价值 v、最多 c 件
int rest = c;
for (int k = 1; k <= rest; k <<= 1) {
    // 把 k 件打包成一件新物品，然后当 0/1 处理
    for (int j = V; j >= k * w; --j)
        dp[j] = max(dp[j], dp[j - k * w] + k * v);
    rest -= k;                       // 这 k 件已经被打包掉了
}
if (rest > 0) {                      // 零头单独成一组
    for (int j = V; j >= rest * w; --j)
        dp[j] = max(dp[j], dp[j - rest * w] + rest * v);
}

#include <bits/stdc++.h>
using namespace std;

const int MAXM = 10005;        // m ≤ 10⁴，开 10005
int a[105];
long long dp[MAXM];            // dp[j]：恰好花掉 j 元的方案数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    dp[0] = 1;                            // 花 0 元的唯一方案：什么都不点

    for (int i = 1; i <= n; ++i)          // 逐道菜考虑
        for (int j = m; j >= a[i]; --j)   // 倒序：保证每道菜最多点一次
            dp[j] += dp[j - a[i]];        // 不点这道菜 + 点这道菜

    cout << dp[m] << "\n";                // 恰好花完 m 元的方案数
    return 0;
}