【例9.13】庆功会

题目描述

班级庆功会拨款买奖品，已知 $n$ （ $n \leqslant 500$ ）种奖品的单价 $v_i \leqslant 100$ 、单件价值 $w_i \leqslant 1000$ 、限购数量 $s_i \leqslant 10$ ，拨款总额 $m \leqslant 6000$ ，求能取得的最大总价值。

输入第一行为 $n\,m$ ；随后 $n$ 行每行 $v\;w\;s$ 。输出一个数：最大价值（注意是价值不是价格）。样例：输入 5 1000 / 80 20 4 / 40 50 9 / 30 50 7 / 40 30 6 / 20 20 1，输出 1040。

思路

多重背包的标准做法：把每种奖品的限购 $s$ 拆成 $1,2,4,\dots$ 及余数共约 $\log s$ 个捆绑份，每份看成一个 0/1 物品；对所有捆绑份跑一维 0/1 背包，预算 $j$ 从大到小更新保证只读旧值，时间 $O(nm\log s)$ 、空间 $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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def split_pieces(stock: int) -> list[int]:
    """把最大购买量 stock 拆成 1,2,4,... 的二进制份：任取 0..stock 件都能由若干份凑出。"""
    pieces: list[int] = []
    k = 1
    while k <= stock:
        pieces.append(k)
        stock -= k
        k <<= 1
    if stock:
        pieces.append(stock)  # 拆剩下的余数单独成一份
    return pieces


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)  # n 种奖品，拨款 m

    dp = [0] * (m + 1)  # dp[j]：预算不超过 j 时能取得的最大总价值
    for _ in range(n):
        price, value, stock = next(data), next(data), next(data)
        for piece in split_pieces(stock):
            cost = piece * price  # 这一份捆绑的整体价格
            if cost > m:
                break             # 二进制份只会越来越大，后面的份必然也超预算
            gain = piece * value  # 这一份捆绑的整体价值
            # 0/1 背包：dp[j] = max(dp[j], dp[j-cost]+gain)；两侧读的都是旧值
            dp[cost:] = map(max, dp[cost:], (old + gain for old in dp))

    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
60
61
62
63
64
65/**
 * 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
 */

#include <cstdio>

typedef long long ll;

const int MAXM = 6005;      // 拨款金额上限
const int MAXPIECE = 15000; // 二进制拆分后总份数上界：n * (log2(s)+1) ≤ 500*5

int n, m;                 // n 种奖品，拨款 m
int v[MAXPIECE];          // 每份捆绑的价格
int w[MAXPIECE];          // 每份捆绑的价值
int piece_cnt;            // 二进制拆分后总份数

ll dp[MAXM];              // dp[j]：预算不超过 j 时能取得的最大总价值

// 读取输入并把每种奖品按限购 s 二进制拆分成若干份捆绑
void read_input() {
    scanf("%d %d", &n, &m);
    piece_cnt = 0;
    for (int i = 0; i < n; ++i) {
        int price, value, stock;
        scanf("%d %d %d", &price, &value, &stock);
        // 把 stock 拆成 1, 2, 4, ..., 剩余；任取 0..stock 件都可由若干份凑出
        int k = 1;
        while (k <= stock) {
            v[piece_cnt] = k * price;
            w[piece_cnt] = k * value;
            ++piece_cnt;
            stock -= k;
            k <<= 1;
        }
        if (stock > 0) {
            v[piece_cnt] = stock * price;
            w[piece_cnt] = stock * value;
            ++piece_cnt;
        }
    }
}

// 0/1 背包：每份捆绑看成一个 0/1 物品，预算 j 从大到小保证只读旧值
void solve() {
    for (int i = 0; i < piece_cnt; ++i) {
        int cost = v[i];
        if (cost > m) continue;  // 同一奖品后续份只会更贵，跳过
        int gain = w[i];
        for (int j = m; j >= cost; --j) {
            ll cand = dp[j - cost] + gain;
            if (cand > dp[j]) dp[j] = cand;
        }
    }
    printf("%lld\n", dp[m]);
}

int main() {
    read_input();
    solve();
    return 0;
}

目录

题目描述

思路

参考代码