题意

给出总预算 N 和 m 件物品。

每件物品有：

• 价格 v
• 重要度 w

如果买下它，就会贡献一份满意度：

• v * w

要求在总花费不超过 N 的前提下，让满意度总和最大。每件物品最多买一次。

思路

一句话本质：把每件物品的"价值"算成价格 × 重要度，这道题就退化成一个标准 01 背包。

先看最直接的暴力：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n, m = data[0], data[1]
items = []
idx = 2
for _ in range(m):
    v, p = data[idx], data[idx + 1]
    idx += 2
    items.append((v, p))

best = 0
for mask in range(1 << m):
    cost = 0
    value = 0
    for i in range(m):
        if mask >> i & 1:
            v, p = items[i]
            cost += v
            value += v * p
    if cost <= n:
        best = max(best, value)

print(best)

brute.py 枚举所有 $2^m$ 种"买/不买"组合，叶子节点检查总花费，统计满意度。

这个暴力为什么慢？

$m$ 最大 25，$2^{25} \approx 3.3\times 10^7$，已经超时。暴力对每件物品只有选和不选两种决策，本质上在遍历一棵二叉决策树。

如果把暴力看成背包问题，它缺了什么？

暴力的每件物品就是一个 0/1 选择，总花费就是"重量"，总满意度就是"价值"。但题目没有直接给出"价值"——它要求价格乘重要度。只要把 $v \times p$ 先算出来，结构完全和 01 背包一致。

为什么一维就够，不需要记具体选了哪些物品？

因为背包只关心"当前总花费"和"当前总价值"这两个数字，过去的决策被压缩进这两个数字中，不需要记录完整选法。

怎么理解容量倒序？

设 $dp_j$ 表示花费不超过 $j$ 时的最大满意度。处理一件物品时：

• 不买：$dp_j$ 不变
• 买：从 $dp_{j-v}$ 转移，加上价值 $v\cdot p$

如果容量正序，同一件物品可能被重复使用；倒序保证每件物品只参与一次转移。最终答案就是 $dp_N$：

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30005;

int n, m;
// dp[j] 表示花费 j 元能获得的最大价值（价格 × 重要度）。
int dp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int v, p;
        cin >> v >> p;
        int w = v * p;                   // 价值 = 价格 × 重要度
        // 0/1 背包倒序枚举。
        for (int j = n; j >= v; j--) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

复杂度

• 时间复杂度：$O(mN)$
• 空间复杂度：$O(N)$

总结

这题和普通 0/1 背包的区别只有一点：

• 价值不是直接输入，而是 价格 * 重要度

只要先把这一层题意翻译出来，后面的状态设计和转移就和标准模板完全一致了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。