帶刪除背包問題

前言

上禮拜讀書會時老鼠講到了這題，之前有遇到過一次，覺得很有趣，但過太久忘了所以就想把想法記錄下來。

背包問題

先複習一下什麼是背包問題：

有 $n$ 個物品，第 $i$ 個物品有重量 $w_i$ 與價值 $v_i$，背包最多能裝重量 $W$ 的物品，求背包能裝的最大價值。因為每個物品只有 0 or 1 個，所以稱作是 0-1 背包問題。

至於解法，我們可以令 $f(i)$ 為當背包內物品總重為 $i$ 時的最大價值，則 $f(i) = \max(f(i), f(i - w_j) + v_j)$，其中 $j$ 為第 $j$ 個物品。

上面這個是最典型的求最佳解背包問題，但有一另外一種背包問題是求解法數，也就是不管價值，問有幾種方法可以使背包內物品的總重加起來為 $W$。

帶刪除背包問題

其實我不太確定這個問題的正式名稱，如果有人知道可以跟我說一聲。

簡單來說，就是在剛剛求解法數的 0-1 背包問題上多加了一個刪除某個物品的操作，並且在操作後需要馬上輸出答案。

解法

先考慮不帶修改的情況：我們可以令 $f(i)$ 為湊出背包內物品總重為 $i$ 的方法數，則轉移式就是：$f(i) = f(i) + f(i - w_j),\ (f(0) = 1)$，至於帶修改要怎麼做呢？

我們思考一下 $f(i)$ 有什麼特別的地方，假設 $w = \{1, 1, 1, 3\}$，那麼 $f(4) = 3$，因為 $f(4)$ 可由一個 $3$ 與一個 $1$ 組成，而 $1$ 有三種。

雖然 $f(4)$ 看起來只是一個數字，但其實他的背後隱藏著三個集合，分別代表著三種組成 $4$ 的方法：$\{w_1, w_4\}, \{w_2, w_4\}, \{w_3, w_4\}$，我們將這些 $f(i)$ 代表的集合們稱作是 $S(i)$。

那其他 $i$ 呢？我們觀察一下：

• $f(0) = 1, S(0) = \{\}$
• $f(1) = 3, S(1) = \{w_1\}, \{w_2\}, \{w_3\}$
• $f(2) = 3, S(2) = \{w_1, w_2\}, \{w_1, w_3\}, \{w_2, w_3\}$
• $f(3) = 2, S(3) = \{w_1, w_2, w_3\}, \{w_4\}$

那如果我們要將 $w_4$ 刪掉，$S(i)$ 會變成什麼呢？

仔細觀察我們的轉移過程可以發現，$S(i)$ 的組成其實就是所有 $S(i - w_j)$ 加上 $w_j$ 的集合，所以如果我們要刪掉 $w_4$，就是將所有 $S(i - w_4)$ 的集合刪掉，也就是說 $S(i)$ 會變成 $S(i) - S(i - w_4)$。

所以我們要刪掉一個元素的轉移式，其實就是加上一個元素的轉移式反過來！也就是 $f(i) = f(i) - (i - w_j)$。

例題 & Code

題目可以參考 ABC 321F

Code 如下：

#include <bits/stdc++.h>
#define Weakoying ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define ll long long
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pqueue priority_queue
#define pb push_back
#define F first
#define S second
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define cmax(a, b) a = (a > b ? a : b)
#define cmin(a, b) a = (a < b ? a : b)
#define put(x) cout << x << endl;
#define DB(x) cerr << #x << " " << x << endl
#define all(v) v.begin(), v.end()
#define stop system("pause");
#define MEM(x, n) memset(x, n, sizeof(x));
#define lowbit(x) x &(-x)
#define SZ(v) ((int)v.size())
#if !LOCAL
#define endl "\n"
#pragma GCC optimize("Ofast", "unroll-all-loops")
#endif
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int P = 998244353;

using namespace std;
/******************************************************************************/
#define MAXN 5005
#define MAXM 1000005 
int n, m;
int dp[MAXN];

void sol() {
    cin >> n >> m;
    dp[0] = 1;
    char c;
    int x;
    for (int i = 0; i < n; i++) {
        cin >> c >> x;
        if (c == '+') {
            for (int i = m; i >= x; i--) {
                dp[i] += dp[i - x];
                dp[i] %= P;
            }
        }
        else {
            for (int i = x; i <= m; i++) {
                dp[i] -= dp[i - x];
                dp[i] = (dp[i] % P + P) % P;
            }
        }
        cout << dp[m] << endl;
    }
}

signed main() {
    Weakoying;
    int t = 1;
    //while (cin >> t)
	{
    	while (t--) {
            sol();
        }
    }
        
    return 0;
}