混合背包

题目描述

背包容量 $M$ （ $M \le 200$ ），有 $N$ 件物品（ $N \le 30$ ），第 $i$ 件重量 $W_i$ 、价值 $C_i$ 、可取件数 $P_i$ ： $P_i = 0$ 表示无限件， $P_i = 1$ 表示只能取一次， $P_i > 1$ 表示至多取 $P_i$ 件。求总重量不超过 $M$ 时的最大总价值。

输入第一行为 $M$ 、 $N$ ，之后 $N$ 行每行三个整数 $W_i$ 、 $C_i$ 、 $P_i$ ；输出一行一个整数表示最大总价值。样例输入为 10 3、2 1 0、3 3 1、4 5 4，输出 11。

思路

用一维滚动数组 dp[j] 表示容量 $j$ 能获得的最大价值：完全背包（ $P=0$ ）正序更新，允许同一物品重复选取；01 背包与多重背包倒序更新，避免重复选取。多重背包把 $P$ 二进制拆成 $1, 2, 4, \dots$ 件一组当 01 物品处理，任意取法都能凑出。时间复杂度 $O(NM + M\sum \log P_i)$ ，空间 $O(M)$ 。

参考代码

Python 版：

python

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
40
41
42
43
44
45#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:38
# update_at: 2026-09-30 02:38

import sys


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    m = next(it)          # 背包容量
    n = next(it)          # 物品数量
    dp = [0] * (m + 1)    # dp[j] 表示容量 j 能获得的最大价值

    for _ in range(n):
        w = next(it)      # 单件重量
        c = next(it)      # 单件价值
        p = next(it)      # 可取件数：0 表示无限

        if p == 0:
            # 完全背包：正序，让同一物品被重复选取
            for j in range(w, m + 1):
                dp[j] = max(dp[j], dp[j - w] + c)
        else:
            # 有限件时按二进制拆成若干 01 背包物品
            k = 1
            while k <= p:
                wt, ct = k * w, k * c
                for j in range(m, wt - 1, -1):
                    dp[j] = max(dp[j], dp[j - wt] + ct)
                p -= k
                k <<= 1
            if p:
                wt, ct = p * w, p * c
                for j in range(m, wt - 1, -1):
                    dp[j] = max(dp[j], dp[j - wt] + ct)

    print(dp[m])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:38
 * update_at: 2026-10-05 07:38
 */
// main.cpp：混合背包，一维滚动数组按物品类型选择正序或倒序更新。
#include <cstdio>

typedef long long ll;

const int MAXM = 205;

ll dp[MAXM]; // dp[j] 表示容量为 j 时能获得的最大价值
ll m, n;     // 背包容量、物品数量

// 01 背包物品：倒序更新，保证 dp[j - w] 是还没选当前物品的旧值
void pack01(ll w, ll c) {
    for (ll j = m; j >= w; j--) {
        if (dp[j - w] + c > dp[j]) {
            dp[j] = dp[j - w] + c;
        }
    }
}

// 完全背包物品：正序更新，允许同一物品被重复选取
void pack_full(ll w, ll c) {
    for (ll j = w; j <= m; j++) {
        if (dp[j - w] + c > dp[j]) {
            dp[j] = dp[j - w] + c;
        }
    }
}

int main() {
    scanf("%lld %lld", &m, &n);
    for (ll i = 1; i <= n; i++) {
        ll w, c, p;
        scanf("%lld %lld %lld", &w, &c, &p);

        if (p == 0) {
            pack_full(w, c); // 无限件
        } else {
            // 有限件：二进制拆成 1,2,4,... 件一组的 01 物品，任意取法都能凑出
            ll k = 1;
            while (k <= p) {
                pack01(k * w, k * c);
                p -= k;
                k = k * 2;
            }
            if (p > 0) {
                pack01(p * w, p * c);
            }
        }
    }
    printf("%lld\n", dp[m]);
    return 0;
}

目录

题目描述

思路

参考代码