疯狂的背包问题(11) - 混合背包问题

题意

$N$ 种物品，容量 $V$ 。每种物品有不同的类型标记 $s_i$ ： $s_i = -1$ 表示只有 1 件（01背包）， $s_i = 0$ 表示有无限件（完全背包）。求最大总价值。

思路

一句话本质：不同物品的限制不同，不需要统一——01 物品倒序取一次，完全物品正序取多次，三种转移独立，放在同一个 dp 里即可。

先看暴力枚举：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40import sys


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    V = next(it)
    items = []
    for _ in range(N):
        v = next(it)
        w = next(it)
        s = next(it)
        items.append((v, w, s))

    ans = 0

    def dfs(idx: int, cur_vol: int, cur_val: int) -> None:
        nonlocal ans
        if cur_vol > V:
            return
        if idx == N:
            if cur_vol <= V:
                ans = max(ans, cur_val)
            return
        v, w, s = items[idx]
        if s == -1:
            dfs(idx + 1, cur_vol, cur_val)
            dfs(idx + 1, cur_vol + v, cur_val + w)
        else:
            max_cnt = (V - cur_vol) // v
            for cnt in range(max_cnt + 1):
                dfs(idx + 1, cur_vol + cnt * v, cur_val + cnt * w)

    dfs(0, 0, 0)
    print(ans)


if __name__ == '__main__':
    solve()

暴力对每个物品用 DFS 枚举选择次数：01 物品枚举 0/1，完全物品枚举 0 到可装最大数量。当 $N=1000$ 、 $V=1000$ 时，每个完全物品最多有 1000 个选择量，搜索树指数级膨胀，完全不可行。

不同物品的选取规则不一样，能不能用同一个 DP 做？

可以。不管是 01 还是完全，本质上都是"用容量换价值"这个转移。区别只在于：

01 背包每个物品只能选一次，所以倒序枚举容量 $j$ ，确保用到的 dp[j-v] 是上一轮未选当前物品的状态；
完全背包每个物品可以选多次，所以正序枚举容量 $j$ ，dp[j-v] 可能是本轮已经选过该物品的状态，自然实现"无限次"。

那混合背包怎么做？

读入每个物品时，检查它的类型标记 $s_i$ ：

$s_i = -1$ （01）：用 for (j = V; j >= v; j--) 倒序转移一次；
$s_i = 0$ （完全）：用 for (j = v; j <= V; j++) 正序转移一次。

两者用同一个 dp 数组，顺序处理每个物品即可。关键是 01 物品倒序、完全物品正序，互不干扰。

为什么正序/倒序就能控制次数？

把 DP 过程想象成一张一维表。倒序时， $j$ 从大到小走，算 dp[j] 时参考的 dp[j-v] 还在"表格左边"没被本轮更新过，所以是上一轮的状态——对应"最多选一次"。正序时，dp[j-v] 可能已经被本轮更新过，所以一个物品可以在这个容量段反复贡献——对应"可以选多次"。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
// dp[c] 表示容量为 c 时的最大价值。
int dp[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V;
    cin >> N >> V;
    for (int i = 0; i < N; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == -1) {                     // 0/1 背包：倒序枚举避免重复使用
            for (int j = V; j >= v; j--)
                dp[j] = max(dp[j], dp[j - v] + w);
        } else {                            // 完全背包：正序枚举，允许多次取用
            for (int j = v; j <= V; j++)
                dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

时间 $O(NV)$ ，每个物品遍历一次容量 $V$ 做转移。空间 $O(V)$ ，只有一维 dp 数组。

总结

混合背包不需要发明新算法，本质是 01 和完全的缝合：01 物品用倒序，完全物品用正序，放在同一轮循环里就行。区分 01/完全的核心不是物品本身，而是枚举顺序。

疯狂的背包问题(11) - 混合背包问题

目录

题意

思路

代码

复杂度

总结