混合背包

1 问题引入

前面的三种背包，区别只在「每种物品能用几次」：

类型	可用次数
01 背包	恰好 1 次
完全背包	无限次
多重背包	不超过 $m_i$ 次

如果一张图里三种物品同时出现呢？

定义混合背包

有 $n$ 件物品和一个容量为 $C$ 的背包。第 $i$ 件物品给出重量 $w_i$ 、价值 $v_i$ ，以及一个标记 $p_i$ ： $p_i=1$ 表示只能用一次， $p_i=0$ 表示能用无限次， $p_i>1$ 表示最多用 $p_i$ 次。求最大价值。

样例：

2 关键：循环方向

回看 01 背包和完全背包的一维写法，两者只差一个地方：

// 01 背包：容量倒序
for (int j = C; j >= w; --j) f[j] = max(f[j], f[j-w] + v);

// 完全背包：容量正序
for (int j = w; j <= C; ++j) f[j] = max(f[j], f[j-w] + v);

为什么方向能决定「用几次」？

倒序时，算 $f[j]$ 用到的 $f[j-w]$ 还是上一轮（没考虑当前物品）的值，所以当前物品最多被放一次；
正序时， $f[j-w]$ 已经是本轮更新过的值，也就是「已经放过当前物品」的结果，于是可以接着再放，形成无限次。

所以混合背包根本不需要新的状态设计——按物品种类选择循环方向即可。

3 朴素写法

先给一份完全按定义写的版本，用二维数组，便于对照理解：

// 混合背包：朴素写法
// 每件物品给 w v p：p=1 只能用一次（01），p=0 能用无限次（完全），p>1 最多用 p 次（多重）
// 按类别分别处理，f[i][j] 前 i 件、容量 j 的最大价值
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

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

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= C; ++j) {
            f[i][j] = f[i - 1][j];                        // 一件也不选
            int limit = (p[i] == 0) ? j / w[i] : min(p[i], j / w[i]);
            for (int k = 1; k <= limit; ++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;
}

输出：

4 一维写法

把二维压成一维，三种情况分别处理：

$p=1$ ：容量倒序；
$p=0$ ：容量正序；
$p>1$ ：拆成 $p$ 件 01 物品，每件都倒序。

// 混合背包：一维数组 + 循环方向
// 01 背包容量倒序（保证每件只用一次），完全背包容量正序（允许重复用同一件），
// 多重背包拆成若干件 01 物品
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

int n, C;
int f[maxn];

int main() {
    cin >> n >> C;
    for (int i = 1; i <= n; ++i) {
        int w, v, p;
        cin >> w >> v >> p;

        if (p == 0) {                       // 完全背包：容量正序
            for (int j = w; j <= C; ++j) f[j] = max(f[j], f[j - w] + v);
        }
        else if (p == 1) {                  // 01 背包：容量倒序
            for (int j = C; j >= w; --j) f[j] = max(f[j], f[j - w] + v);
        }
        else {                              // 多重背包：朴素拆成 p 件
            for (int k = 1; k <= p; ++k) {
                for (int j = C; j >= w; --j) f[j] = max(f[j], f[j - w] + v);
            }
        }
    }
    cout << f[C] << endl;
    return 0;
}

输出：

5 多重部分用二进制拆分

上面的 $p>1$ 分支是「一件一件拆」，复杂度 $O(p)$ 。用多重背包那一讲的二进制拆分，可以降到 $O(\log p)$ ：

// 混合背包：多重部分用二进制拆分
// 把 p 件拆成系数 1,2,4,...,余数 的若干件，任意 0..p 的取法都能凑出，
// 于是多重背包也变成一堆 01 物品
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

int n, C;
int f[maxn];
int iw[maxn * 20], iv[maxn * 20], icnt;

void zero_one(int w, int v) {              // 一件 01 物品
    for (int j = C; j >= w; --j) f[j] = max(f[j], f[j - w] + v);
}

int main() {
    cin >> n >> C;
    for (int i = 1; i <= n; ++i) {
        int w, v, p;
        cin >> w >> v >> p;

        if (p == 0) {                       // 完全背包：直接正序
            for (int j = w; j <= C; ++j) f[j] = max(f[j], f[j - w] + v);
        }
        else {                              // 01 与多重统一按件拆开
            for (int k = 1; k <= p; k <<= 1) { zero_one(k * w, k * v); p -= k; }
            if (p > 0) zero_one(p * w, p * v);
        }
    }
    cout << f[C] << endl;
    return 0;
}

输出：

说明三份程序的关系

simple.cpp 是照定义直译的参照实现；one_dim.cpp 和 binary.cpp 是优化版。三份程序在同一份输入上输出一致（都是 20），这一点在仓库里用暴力枚举对拍验证过。

6 抽象出三个过程

如果三种背包各自写成一个函数，混合背包的主循环会非常干净：

for (int i = 1; i <= n; ++i) {
    if (p[i] == 1)      ZeroOnePack(f, w[i], v[i]);
    else if (p[i] == 0) CompletePack(f, w[i], v[i]);
    else                MultiplePack(f, w[i], v[i], p[i]);
}

这正是《背包问题九讲》强调的一点：把每种背包处理成「一件物品的过程」，之后无论怎么组合都不会乱。

7 小结

混合背包是「抽象」带来的收益最直观的一讲：只要三种基本背包各自封装好，混合起来不过是加几个 if。

真正需要记住的只有一件事——倒序 = 只用一次，正序 = 可用无限次。后面遇到任何「循环方向」的疑惑，回到这句话就能想清楚。

8 相关题解

暂无相关题解