[NOIP2006-普及] 开心的金明

题目描述

金明有 $N$ 元钱要买 $m$ 件物品，第 $j$ 件价格 $v_j$ 、重要度 $w_j$ ，每件至多买一次，求总价不超过 $N$ 时 $\sum v_j w_j$ 的最大值。（ $N<30000$ ， $m<25$ ， $v\le 10000$ ， $1\le w\le 5$ 。）输入第一行 $N\ m$ ，随后 $m$ 行每行 $v\ p$ ；输出该最大值。样例：输入 1000 5 / 800 2 / 400 5 / 300 5 / 400 3 / 200 2，输出 3900。

思路

把每件物品看成重量 $v_j$ 、价值 $v_j w_j$ 的 0/1 背包，容量为 $N$ 。设 $f[c]$ 为花费不超过 $c$ 的最大乘积和，逐件物品倒序枚举 $c=N,\dots,v_j$ ，用 $f[c]=\max(f[c],\,f[c-v_j]+v_jw_j)$ 滚动更新。倒序保证下标 $c-v_j$ 尚未被本件物品更新，从而每件只选一次；时间 $O(mN)$ 、空间 $O(N)$ 。

参考代码

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#!/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-10-02 06:42
# update_at: 2026-10-02 06:42

import sys


def knapsack(budget: int, items: list[tuple[int, int]]) -> int:
    """0/1 背包：容量 budget、每件物品用一次，最大化 Σ 价格×重要度。"""
    dp = [0] * (budget + 1)  # dp[c] = 花费不超过 c 时的最大乘积和
    for v, p in items:
        gain = v * p
        # 倒序枚举容量，物品只能从"还没选过它的状态"转移，保证只选一次
        for c in range(budget, v - 1, -1):
            take = dp[c - v] + gain  # 选这件物品
            if take > dp[c]:
                dp[c] = take
    return dp[budget]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    budget, m = next(data), next(data)  # 总钱数 N、物品个数 m
    items = [(next(data), next(data)) for _ in range(m)]  # (价格, 重要度)
    print(knapsack(budget, items))


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/**
 * 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-06 13:35
 * update_at: 2026-10-06 13:35
 */
#include <cstdio>
#include <algorithm>

typedef long long ll;

const int MAXN = 30005; // 总钱数 N < 30000，多开几位防止越界

ll dp[MAXN]; // dp[c] 表示花费不超过 c 时，价格与重要度乘积和的最大值

int main() {
    int budget, m;
    scanf("%d %d", &budget, &m);

    for (int i = 1; i <= m; i++) {
        ll price, weight;
        scanf("%lld %lld", &price, &weight);
        ll gain = price * weight; // 选这件物品获得的乘积值
        // 倒序枚举容量，保证 dp[c - price] 还是上一件物品的结果，每件物品只选一次
        for (int c = budget; c >= price; c--) {
            dp[c] = std::max(dp[c], dp[c - price] + gain);
        }
    }

    printf("%lld\n", dp[budget]);
    return 0;
}

[NOIP2006-普及] 开心的金明

目录

题目描述

思路

参考代码