多重背包

01 背包中每个物品只有一个，而多重背包中每个物品有 $s_i$ 个。

多重背包二进制优化

对于第 $i$ 个物品，如果它有 $s_i$ 个，就将其用二进制拆分，然后转成 01 背包。

如 $13 = 1 + 2 + 4 + 6$。

注意拆分时，拆出来的物品也要修改它的价值。

复杂度：$O(W \sum\limits_{i=1}^n \log s_i)$，其中 $W$ 为背包容量。

代码 
int n, V;
int dp[2005];

void pack01(int v, int w) {
    for (int j = V; j >= v; j--) {
        dp[j] = max(dp[j], dp[j-v] + w);
    }
}

int main() {
    cin >> n >> V;
    while (n--) {
        int v,w,s; cin >> v >> w >> s;
        int k = 1;
        while (k <= s) {
            pack01(v*k, w*k);
            s -= k;
            k <<= 1;
        }
        pack01(v*s, w*s);
    }
    int ans = 0;
    for (int j = 0; j <= V; j++) ans = max(ans, dp[j]);
    cout << ans << endl;
}

多重背包（单调队列优化）

设 $f_j$ 为装容量为 $j$ 的最大价值，$i$ 为当前考虑的物品，有 $s_i$ 个。

暴力跑多重背包的转移方程是：

$$f_j = \max\limits_{k \in [0,s_i]} f_{j-kw_i} + kv_i$$

这显然是一个滑动窗口的模版，只不过这个窗口是按同余类来的，比如 $j=10$，而 $w_i=3$，$s_i=2$，那么转移 $f_{10}$ 时由 $f_7, f_4$ 来转移。

于是枚举同余类，然后对于每一个同余类都用滑动窗口来优化即可。

复杂度：$O(nW)$，其中 $n$ 为物品种类数。

代码 
struct node {
    int pos, val;
} q[20005];
int head = -1, tail = 0, n, V, dp[20005];

void solve(int v, int w, int s) {
    for (int j = 0; j < v; j++) {
        head = 0, tail = -1;
        q[++tail] = {0,0};
        for (int i = 1; i*v + j <= V; i++) {
            while (i - q[head].pos > s) head++;
            int cur = i*v + j;
            int val = dp[cur] - i*w;
            dp[cur] = max(dp[cur], q[head].val + i*w);

            while (head <= tail && val >= q[tail].val) tail--;
            q[++tail] = {i, val};
        }
    }
}

int main() {
    cin >> n >> V;
    for (int i = 1; i <= n; i++) {
        int v,w,s; cin >> v >> w >> s;
        solve(v,w,s);
    }
    int ans = 0;
    for (int j = 0; j <= V; j++) ans = max(ans, dp[j]);
    cout << ans << endl;
}

分组背包

01背包的变形，每一个物品只有一个，但它属于某个组，一个组内只能选最多一个物品。

只要对每一组来跑 01 背包即可。

代码 
int dp[1005];
int W, n;
vector<pii> adj[105];
void pack01(int k) {
    for (int w = W; w >= 0; w--) {
        for (auto [c, v] : adj[k]) {
            if (w >= c) dp[w] = max(dp[w], dp[w-c] + v);
        }
    }
}
int main() {
    cin >> W >> n;
    for (int i = 1; i <= n; i++) {
        int w, v, k; cin >> w >> v >> k;
        adj[k].push_back({w, v});
    }
    for (int k = 1; k <= 100; k++) pack01(k);
    cout << dp[W] << endl;
}

背包删除元素

众所周知，背包内加入一个元素是（这里 dp[i] 代表能够装重量和为 $i$ 的物品的方案数）：

for (int i = N; i >= w; i--) dp[i] += dp[i - w];

而背包删除一个元素其实也可以反过来做：

for (int i = w; i <= N; i++) dp[i] -= dp[i - w];

• 注意这里的枚举顺序，在删除的时候要保证删除时，用的是加入前的状态，所以是从小到大删。

例题

例1 Google Kickstart 2022 RoundH D. Level Design

题意

给定一个长度为 $n$ 的permutation。

如果把permutation看作一个图（第 $i$ 位的值是 $p_i$ 的话，那么有 $i \rightarrow p_i$）。

我们可以对这个 permutation 进行任意次数的 swap 操作，每次交换任意的 $p_i, p_j$ 的位置。

现在对于每一个 $k \in [1,n]$，回答：

最少需要多少次 swap 操作，使得，得到的图中至少有一个大小为 $k$ 的cycle。

其中，$n \leq 10^5$，每个回答各自独立。

题解

首先经过一些观察，可以发现：

使用 $1$ 次操作，可以让一个cycle合并到另外一个cycle上去，或者也可以将一个大的 cycle 拆成 $2$ 个小cycle。

所以我们先用 DFS 求出所有 cycle 的大小。

然后就是一个背包问题：

有 $n$ 个物品，每个物品有一个大小 $a_i$，并且每次装到背包中有一个 cost $1$。

也可以将一个物品分成两个更小的物品，分割的 cost 也为 $1$。

对于每一个可能的背包大小 $k \in [1,n]$，求最少的cost使得这个背包刚好被装满？

注意到分割操作只有最多一次，因为可以先装背包，将背包装多一点，然后分掉一个使得背包刚好装满。

那装背包的话，物品数量太多了怎么办？

想到 多重背包的二进制背包优化，那个是将大的拆成小的。我们也可以将小的合成为大的。

比如有 $3$ 个大小为 $1$ 的物品，每个cost均为 $1$，我们就可以将其中 $2$ 个合成为一个大小为 $2$，cost为 $2$ 的大物品。

所以对于大小为 $x$，cost为 $c$ 的物品，如果它有 $\geq 3$ 个，就将其中 $2$ 个合成为大小为 $2x$，cost为 $2c$ 的物品。

时间复杂度：所有物品的大小之和为 $n$，所以物品大小的种类数只有 $O(\sqrt n)$ 个。在合并之后，物品的数量不会超过 $O(\sqrt n * \log(10^5))$ 个。

所以就可以跑背包了，复杂度为 $O(n \sqrt n)$。

• 注意背包枚举的时候，外层循环是物品，里层循环是大小。

• 注意到装第一个物品的 cost 为 $0$，这个直接用 dp[0] = -1 来表示。

// 背包枚举顺序：外层是物品，里层是大小
for (pii a : item_vec) {
    for (int i = n; i >= 1; i--) {
        int item_sz = a.first, cost = a.second;
        if (item_sz > i) break;
        dp[i] = min(dp[i], dp[i-item_sz] + cost);
    }
}
代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int maxm = 1e8+5;

int T;
int n, p[maxn];
bool vis[maxn];
// int cnt[maxn];
map<int, int> items[maxn];  // items[i]: 大小为 i 的所有物品的 cost  (key: cost, value: cnt)
vector<pii> item_vec;
int dp[maxn];
int main() {
    cin >> T;

    for (int t = 1; t <= T; t++) {
        cin >> n;
        item_vec.clear();
        for (int i = 1; i <= n; i++) {
            cin >> p[i];
            vis[i] = 0, items[i].clear(), dp[i] = 1e9;
        }
        dp[0] = -1;
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                int sz = 0;
                int u = i;
                do {
                    vis[u] = 1;
                    sz++;
                    u = p[u];
                } while (!vis[u]);
                items[sz][1]++;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (auto& itr : items[i]) {
                int cost = itr.first;
                while (itr.second >= 3) {
                    itr.second -= 2;
                    items[i*2][cost*2] += 1;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (auto itr : items[i]) {
                int cost = itr.first, cnt = itr.second;
                while (cnt--) {
                    item_vec.push_back({i, cost});  // 大小, cost
                }
            }
        }

        // 背包枚举顺序：外层是物品，里层是大小
        for (pii a : item_vec) {
            for (int i = n; i >= 1; i--) {
                int item_sz = a.first, cost = a.second;
                if (item_sz > i) break;
                dp[i] = min(dp[i], dp[i-item_sz] + cost);
            }
        }

        int mn = 1e9;
        // 考虑拆分物品（最多一次）
        for (int i = n; i >= 1; i--) {
            dp[i] = min(dp[i], mn + 1);
            mn = min(mn, dp[i]);
        }
        cout << "Case #" << t << ": ";
        for (int i = 1; i <= n; i++) cout << dp[i] << " ";
        cout << endl;
    }
}

例2 CF95E Lucky Country

题意

给定 $n$ 个点，$m$ 条边的无向图。

每次操作可以加一条边。

求最少的操作次数，使得其中一个联通块的大小为 $x$，且 $x$ 只包含 $4,7$ 这两个字符。

其中，$n,m \leq 10^5$，如果操作不存在输出 $-1$。

题解

把联通块大小看作数字，就是每次操作合并两个数字，看怎么样合并出一个 $x$ 只包含 $4,7$ 这两个字符。

一眼多重背包，但数据范围太大了。

再次注意到所有数字的和为 $n$（多重背包二进制的经典老套路），所以不同的数字种类最多为 $O(\sqrt n)$ 个。

于是拿二进制优化一下多重背包就可以 $O(n \sqrt n \log(10^5))$ 跑出来了（实际上复杂度上界很松）。

• 注意二进制合并物品的时候，也要增加相应的 cost。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+55;
const int maxm = 4e4+55;

bool isLukcy(int x) {
    while (x) {
        int r = x % 10;
        x /= 10;
        if (r != 4 && r != 7) return 0;
    }
    return 1;
}


int dp[maxn], par[maxn], sz[maxn];
int finds(int u) {
    if (par[u] == u) return u;
    return par[u] = finds(par[u]);
}

void unions(int u, int v) {
    u = finds(u), v = finds(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u,v);
    sz[u] += sz[v], sz[v] = 0;
    par[v] = u;
}
int n, m, cnt[maxn];


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        unions(u,v);
    }
    vector<int> vec;
    for (int i = 1; i <= n; i++) {
        if (par[i] == i) vec.push_back(sz[i]);
    }

    for (int x : vec) cnt[x]++;
    vector<pii> res;
    for (int i = 1; i <= 100000; i++) {
        if (cnt[i]) {
            for (int j = 1; j <= cnt[i]; j *= 2) {
                cnt[i] -= j;
                res.push_back({j * i, j});
            }
            if (cnt[i]) res.push_back({cnt[i] * i, cnt[i]});
        }
    }

    memset(dp, 63, sizeof(dp));
    dp[0] = 0;
    for (auto [x, c] : res) {
        for (int i = 100000; i >= x; i--) {
            dp[i] = min(dp[i], dp[i-x] + c);
        }
    }

    int ans = 1e9;
    for (int i = 1; i <= n; i++) {
        if (isLukcy(i)) {
            ans = min(ans, dp[i]);
        }
    }
    cout << ((ans > 1e8) ? -1 : ans - 1) << endl;
}

例3 The Knapsack problem

题意

给定 $n$ 个物品，第 $i$ 个物品的大小为 $w_i$，价值为 $c_i$，每个物品有无数个。

给定一个大小为 $S$ 的背包，求最大价值。

其中，$n,w_i \in [1,10^3], S,c_i \in [0,10^9]$。

题解

完全背包，但是大小为 $10^9$？

不过我们可以发现：一个大小为 $S$ 的背包的最优解肯定能分成两个大小为 $S_1,S_2$ 的背包，使得：

  1. $S_1 + S_2 = S$，且
  2. $|S_1-S_2| \leq \max w_i \leq 1000$

因为如果 $|S_1-S_2| > 1000$ 的话，那么将大的那个背包，拿出一个元素塞给小的背包，则两者之差会减去 $2000$，这样就会保证 $|S_1-S_2| < 1000$ 了。

所以要求大小为 $S$ 的背包，不妨分治解决 $S_1,S_2$ 大小的背包，其中

$$S_1, S_2 \in [\frac{S}{2} - 1000, \frac{S}{2} + 1000]$$

这样就可以一直分治下去，我们预处理出来 $4000$ 以内的答案，更大的用分治来解决即可。

• 因为时限只有 1 秒，所以不能用递归。但是注意到每一层需要求出的背包大小是一个连续的区间，如第一层是 $[S,S]$，第二层是 $[\frac{S}{2} - 1000, \frac{S}{2} + 1000]$，每一层都是根据上一层的左右端点 / 2 以后往外延伸。

这样就不用递归，直接一层一层的处理即可。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;

int M = 1000;
int n, S, w[maxn], c[maxn];
ll dp[maxn];
vector<ll> dp2[30];
int L[30], R[30];
int main() {
    cin >> n >> S;
    for (int i = 1; i <= n; i++) cin >> w[i] >> c[i];

    for (int i = 1; i <= n; i++) {
        for (int j = w[i]; j <= 4*M; j++) {
            dp[j] = max(dp[j], dp[j-w[i]] + c[i]);
        }
    }

    L[1] = S, R[1] = S;

    int d;
    for (d = 2; ; d++) {
        L[d] = max(0, L[d-1] / 2 - M), R[d] = min(S, (R[d-1] + 1) / 2 + M);  
        // 注意这里是 `R[d] = (R[d-1] + 1)`，保证 R[d] 不会因为整除的问题而导致 dp2[d] 中数量不够
        if (R[d] <= 4*M) break;
    }

    for (; d >= 1; d--) {
        for (int j = L[d]; j <= R[d]; j++) {
            if (j <= 4*M) dp2[d].push_back(dp[j]);
            else {
                ll res = 0;
                for (int k = max(L[d+1], j/2 - M); k <= min(R[d+1], j/2 + M); k++) {
                    int i1 = k - L[d+1], i2 = j - k - L[d+1];
                    res = max(res, dp2[d+1][i1] + dp2[d+1][i2]);
                }
                dp2[d].push_back(res);
            }
        }
    }
    cout << dp2[1][0] << endl;
}