[NOIP 2006 普及组] 开心的金明

题意

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

每件物品有：

价格 v
重要度 w

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

v * w

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

思路

先看最直接的暴力：

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// brute.cpp：小数据暴力解，使用 01 序列枚举每件物品买或不买。
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1005;

int budget;             // 总预算
int item_count;         // 物品数量
int price[MAXM];        // 价格
int importance[MAXM];   // 重要度
int choose_item[MAXM];  // choose_item[i] = 0/1，表示第 i 件物品不买/买
int best_answer;        // 当前最大满意度

bool check() {
    int used_money = 0;
    for (int i = 1; i <= item_count; i++) {
        if (choose_item[i] == 1) used_money += price[i];
    }
    return used_money <= budget;
}

int calc_answer() {
    int total_value = 0;
    for (int i = 1; i <= item_count; i++) {
        if (choose_item[i] == 1) total_value += price[i] * importance[i];
    }
    return total_value;
}

void dfs_choose(int dep) {
    if (dep == item_count + 1) {
        if (check()) {
            int value = calc_answer();
            if (best_answer < value) best_answer = value;
        }
        return;
    }

    // 第 dep 件物品的 01 选择：0 不买，1 买。
    for (int i = 0; i <= 1; i++) {
        choose_item[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    cin >> budget >> item_count;
    for (int i = 1; i <= item_count; i++) {
        cin >> price[i] >> importance[i];
    }

    best_answer = 0;
    dfs_choose(1);

    cout << best_answer << '\n';
    return 0;
}

brute.cpp 把每件物品看成一个 01 选择：choose_item[i] = 0/1 表示不买或买。递归先生成完整选择，叶子节点再检查总花费是否超限，并统计满意度。

这个做法正确，但复杂度是 $O(2^m)$ ，只能做小数据验证。

关键观察是：这题本质上仍然是 0/1 背包，只是物品的“价值”不是直接给出的，而是需要先算：

value = price * importance

于是题目就变成：

预算 N 是背包容量
每件物品最多选一次
物品重量是 price
物品价值是 price * importance

设：

dp[j] 表示花费不超过 j 时，能够得到的最大满意度

加入一件物品时：

不买它：状态不变
买它：从 dp[j - price] 转移，再加上它的价值

所以转移是：

dp[j] = max(dp[j], dp[j - price] + price * importance)

由于每件物品只能买一次，预算维必须倒序枚举。

状态表

这张表说明状态的含义：

状态	含义
`dp[j]`	花费不超过 `j` 时，能够得到的最大满意度

从这个定义可以看出，DP 只关心“花了多少钱”以及“能得到多少满意度”，不需要记录具体买了哪些物品。因此一维状态就足够。

最后输出 dp[N] 即可。

DP 公式

设 $dp_j$ 表示花费不超过 $j$ 时能得到的最大满意度。第 $i$ 件物品价格为 $v_i$ ，重要度为 $p_i$ ，价值为 $v_i p_i$ ，转移为：

dp_j=\max(dp_j,\ dp_{j-v_i}+v_i p_i)

其中 $j\geqslant v_i$ ，且预算倒序枚举。最终答案为：

dp_N

公式解释：物品价格是容量消耗，价格乘重要度才是真正收益。每件物品只买或不买一次，所以从 j-v_i 转移并倒序枚举预算。

代码

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

const int MAXM = 1005;

int budget;             // 总预算
int item_count;         // 物品数量
int price[MAXM];        // 第 i 个物品的价格
int importance[MAXM];   // 第 i 个物品的重要度
vector<int> dp;         // dp[j] = 花费不超过 j 时能获得的最大满意度

void read_input() {
    cin >> budget >> item_count;
    for (int i = 1; i <= item_count; i++) {
        cin >> price[i] >> importance[i];
    }
}

void solve() {
    dp.assign(budget + 1, 0);

    for (int i = 1; i <= item_count; i++) {
        int value = price[i] * importance[i];
        // 倒序枚举预算，保证每个物品最多只买一次。
        for (int j = budget; j >= price[i]; j--) {
            dp[j] = max(dp[j], dp[j - price[i]] + value);
        }
    }

    cout << dp[budget] << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

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

总结

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

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

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

一图流解析

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