多重背包

1 问题引入

01 背包里每种物品只有一件，完全背包里每种物品有无穷多件。中间还有一种情形：每种物品有有限的若干件。

定义多重背包

有 $n$ 种物品和一个容量为 $C$ 的背包。第 $i$ 种物品最多有 $m_i$ 件可用，每件耗费空间 $w_i$ 、价值 $v_i$ 。求在总耗费不超过 $C$ 的前提下能得到的最大价值。

样例：

2 基本思路：直接枚举件数

像完全背包那样，只把「最多选几件」的上界从 $\lfloor C/w_i \rfloor$ 换成 $m_i$ ：

f(i,j)=\max\{\,f(i-1,\,j-k\cdot w_i)+k\cdot v_i \;\big|\; 0\le k\le m_i,\; k\cdot w_i\le j\,\}

$f(i,j)$ 表示前 $i$ 种物品、容量 $j$ 的最大价值。每个状态要枚举 $k$ ，总复杂度

O\Bigl(C\cdot \sum_{i=1}^{n} m_i\Bigr)

比 01 背包多一个 $\sum m_i$ 的因子。数据一大就过不去。

// 多重背包：朴素三重循环
// f[i][j] 前 i 种物品、容量 j 的最大价值，第 i 种可用 m[i] 件
// 时间 O(n * C * sum(m))，直接按「第 i 种选几件」枚举
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

int n, C;
int w[maxn], v[maxn], m[maxn];
int f[maxn][maxn];

int main() {
    cin >> n >> C;
    for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i] >> m[i];

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= C; ++j) {
            f[i][j] = f[i - 1][j];              // 第 i 种选 0 件
            for (int k = 1; k <= m[i] && k * w[i] <= j; ++k) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]);
            }
        }
    }
    cout << f[n][C] << endl;
    return 0;
}

输出：

3 转成 01 背包

最直接的想法是：第 $i$ 种物品最多 $m_i$ 件，那就拆成 $m_i$ 件独立的物品，每件重量 $w_i$ 、价值 $v_i$ ，然后跑 01 背包。

这个想法是对的，但复杂度没变——物品总数还是 $\sum m_i$ 件。

4 二进制拆分

关键观察：要能凑出 $0\sim m$ 之间的任意件数，不需要 $m$ 件物品，只需要 $O(\log m)$ 件。

把 $m$ 拆成

1,\;2,\;4,\;\dots,\;2^{k-1},\;m-2^k+1

其中 $k$ 是满足 $m-2^k+1>0$ 的最大整数。这组数的和恰好是 $m$ ，而且 $0\sim m$ 之间的每个整数都能被某个子集凑出来：

$0\sim 2^k-1$ ：用 $1,2,4,\dots,2^{k-1}$ 的二进制表示凑；
$2^k\sim m$ ：先取最后那一项 $m-2^k+1$ ，剩下的差值落在 $0\sim 2^k-1$ 内，归结为上一类。

以 $m=13$ 为例， $k=3$ ，拆成 $1,2,4,6$ 。验证一下： $9=6+2+1$ ， $11=6+4+1$ ， $13=6+4+2+1$ ，都在其中。

于是第 $i$ 种物品变成 $O(\log m_i)$ 件 01 物品，其中系数为 $t$ 的那件重量是 $t\cdot w_i$ 、价值是 $t\cdot v_i$ 。总复杂度降到

O\Bigl(C\cdot \sum_{i=1}^{n}\log m_i\Bigr)

// 多重背包：二进制拆分 + 01 背包
// 把 m 件同种物品拆成系数 1,2,4,...,余数 的若干件，
// 任意 0..m 的取法都能由这些系数之和表示，于是转成 01 背包。
// 时间 O(n * C * log m)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

int n, C;
int f[maxn];
int iw[maxn * 20], iv[maxn * 20], icnt;   // 拆分后的物品

int main() {
    cin >> n >> C;
    for (int i = 1; i <= n; ++i) {
        int w, v, m;
        cin >> w >> v >> m;
        for (int k = 1; k <= m; k <<= 1) {          // 1,2,4,...
            iw[++icnt] = k * w; iv[icnt] = k * v;
            m -= k;
        }
        if (m > 0) { iw[++icnt] = m * w; iv[icnt] = m * v; }  // 最后一段
    }

    for (int i = 1; i <= icnt; ++i) {                // 01 背包，容量倒序
        for (int j = C; j >= iw[i]; --j) {
            f[j] = max(f[j], f[j - iw[i]] + iv[i]);
        }
    }
    cout << f[C] << endl;
    return 0;
}

输出同样是：

5 单调队列优化到 O(nC)

二进制拆分已经把 $\log m$ 压得很低，但如果 $m$ 本身很大（比如 $10^9$ ，只有上界没有具体件数列表），还能再降一维。

按容量 $j$ 对 $w$ 取模的余数 $r$ 分组，同一组里 $j$ 排成

r,\; r+w,\; r+2w,\;\dots

设 $j=r+q\cdot w$ ，把转移式展开：

f(i,\,r+qw)=\max_{0\le k\le m}\Bigl\{ f(i-1,\,r+(q-k)w)+k\cdot v \Bigr\}

令 $p=q-k$ ，则 $k=q-p$ ，上式变成

f(i,\,r+qw)=q\cdot v+\max_{q-m\le p\le q}\Bigl\{\,f(i-1,\,r+pw)-p\cdot v\,\Bigr\}

括号里那一项只和 $p$ 有关，记作 $g(p)$ 。于是每个 $q$ 要的是 $g$ 在滑动窗口 $[q-m,\,q]$ 上的最大值——这正是单调队列的用武之地，均摊 $O(1)$ 。

总复杂度 $O(nC)$ 。

// 多重背包：单调队列优化到 O(nC)
//
// 关键观察：按容量 j 对 w 取模余数 r 分组，同一组里的 j 排成
//   r, r+w, r+2w, ...
// 设 j = r + q*w，则转移
//   f[i][j] = max{ f[i-1][j-k*w] + k*v }  (0 <= k <= m)
// 令 g[q] = f[i-1][r+q*w] - q*v，可化成
//   f[i][r+q*w] = q*v + max{ g[p] | q-m <= p <= q }
// 这是滑动窗口最大值，用单调队列 O(1) 均摊求解。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

int n, C;
long long f[maxn], g[maxn];
int q[maxn];                       // 单调队列，存下标 p

int main() {
    cin >> n >> C;

    for (int i = 1; i <= n; ++i) {
        int w, v, m;
        cin >> w >> v >> m;
        if (m > C / w) m = C / w;  // 超过容量上限的件数没有意义

        for (int r = 0; r < w && r <= C; ++r) {
            int cnt = (C - r) / w;         // 这一组有 cnt+1 个位置
            for (int p = 0; p <= cnt; ++p) {
                g[p] = f[r + p * w] - 1LL * p * v;
            }
            int head = 0, tail = 0;        // [head, tail)
            for (int p = 0; p <= cnt; ++p) {
                // 弹出窗口左端滑出的
                while (head < tail && q[head] < p - m) ++head;
                // 维护单调递减
                while (head < tail && g[q[tail - 1]] <= g[p]) --tail;
                q[tail++] = p;
                f[r + p * w] = g[q[head]] + 1LL * p * v;
            }
        }
    }
    cout << f[C] << endl;
    return 0;
}

输出：

说明三种写法的取舍

朴素枚举：好写， $O(C\sum m_i)$ ，只在 $m_i$ 很小时可用。
二进制拆分：最常用。 $O(C\sum\log m_i)$ ，代码短，几乎不会写错。
单调队列： $O(nC)$ ，最快但最容易写错（下标、窗口边界、 $g$ 的符号都要小心）。没有性能压力就别上。

6 可行性问题

有一类变体不问最大价值，只问：能否用这些物品恰好凑出某个容量。

此时可以换一种状态设计：设 $f(i,j)$ 表示「用前 $i$ 种物品填满容量 $j$ 之后，最多还剩几件第 $i$ 种物品可用」。 $f(i,j)=-1$ 表示凑不出。

递推分两步：

若 $f(i-1,j)\ge 0$ ，说明前 $i-1$ 种就能凑出 $j$ ，那么第 $i$ 种一件没用， $f(i,j)=m_i$ ；否则 $f(i,j)=-1$ 。
再顺着 $j$ 从小到大扫一遍：若 $f(i,j)>0$ ，说明还有余量，可以用一件第 $i$ 种物品把 $j+w_i$ 也凑出来，于是 $f(i,j+w_i)=\max\{f(i,j+w_i),\,f(i,j)-1\}$ 。

这样每个状态只被常数次更新，复杂度 $O(nC)$ ，而且不需要价值。

7 小结

多重背包是 01 背包和完全背包之间的那一档。核心技巧是二进制拆分：把一个「取 0 到 $m$ 件」的选择，变成 $O(\log m)$ 个「取或不取」的选择。这个技巧不只用于背包，任何「有上界的重复选择」都能套。

三种写法的完整代码都在本文的 code/ 目录下，输出已对齐——用同一份输入跑出来都是 11。

8 相关题解

暂无相关题解