可撤销背包

一、例题：可撤销背包

有 $n$ 件物品，第 $i$ 件物品体积为 $w_i$，每件物品只有一个。对于每件物品 $i$，分别求：丢失它之后，用剩下的物品恰好装满容量 $x$ 的背包，有多少种装法。对每个 $x=1,2,\ldots,m$ 输出装法数对 $10$ 取模后的结果。

例题：P1309 可撤销背包。数据范围为 $n,m\le2000$、$w_i\le2000$。

二、恰好装满的计数 DP

设 dp[x] 表示当前已加入的物品中，恰好凑出体积 $x$ 的子集数量，对 $10$ 取模。

一开始没有物品，只有空集可以凑出体积 $0$，所以 dp[0]=1，其他状态为 $0$。

加入体积为 $w$ 的物品时，每种旧方案有两种选择：不选它，或选它。因此：

这是 01 背包，容量要倒序枚举，避免同一件物品被重复使用。

三、如何撤销一件物品

设加入这件物品前的状态为 old，加入后的状态为 now。对 $x\ge w$，有：

因此可以反过来求：

撤销时要正序枚举容量。这样处理到 $x$ 时，dp[x-w] 已经恢复为 old[x-w]，可以从当前 dp[x] 中减去它。因为答案对 $10$ 取模，减法写成：

dp[x] = (dp[x] - dp[x - w] + 10) % 10;

撤销后，dp[] 就是“不含这件物品”的状态。输出答案后，再用倒序枚举把这件物品加回去，继续处理下一件物品。

四、处理顺序

1. 先把所有物品依次加入 DP，得到完整物品集的状态。
2. 对每件物品：正序撤销它，输出容量 $1$ 到 $m$ 的答案，再倒序把它加回。

样例中物品体积为 $1,1,2$。丢失第 $3$ 件后，剩下两件体积为 $1$ 的物品：容量 $1$ 有 $2$ 种选法，容量 $2$ 有 $1$ 种选法，因此这一行输出 21。

五、参考代码

#include <iostream>
using namespace std;

const int N = 2005;
int w[N], dp[N];

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

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

    dp[0] = 1;

    // 加入所有物品，得到完整物品集的 DP 状态
    for (int i = 1; i <= n; ++i) {
        for (int x = m; x >= w[i]; --x) {
            dp[x] = (dp[x] + dp[x - w[i]]) % 10;
        }
    }

    for (int i = 1; i <= n; ++i) {
        // 正序撤销第 i 件物品
        for (int x = w[i]; x <= m; ++x) {
            dp[x] = (dp[x] - dp[x - w[i]] + 10) % 10;
        }

        for (int x = 1; x <= m; ++x) {
            cout << dp[x];
        }
        cout << '\n';

        // 倒序加回第 i 件物品，恢复完整物品集的状态
        for (int x = m; x >= w[i]; --x) {
            dp[x] = (dp[x] + dp[x - w[i]]) % 10;
        }
    }

    return 0;
}

初始构建、每次撤销和加回都需要 $O(m)$，总时间复杂度为 $O(nm)$，空间复杂度为 $O(n+m)$。