先把每道题的耗时按水平倍率换算出来，再把奖励当价值、耗时当容量做一维 0/1 背包。
OJ: luogu
题目 ID: P2430
难度:普及-
标签:动态规划01背包背包
日期: 2026-06-19 15:09
题意
给出：
- WKY 的水平值
- 老王的水平值
m道题，每道题有所属知识点和奖励值n个知识点，已知老王做该知识点题目的耗时- 总时间上限
T
题目保证老王的水平值是 WKY 的整数倍，所以同一道题里：
WKY 耗时 = 老王耗时 × (老王水平值 / WKY水平值)
每道题最多做一次，要求在总时间不超过 T 的前提下，让 WKY 得到的总奖励值最大。
这张表把样例中的 6 道题翻译成了真正要选的“物品”：
| 题号 | 知识点 | 老王耗时 | WKY 耗时 | 奖励 |
|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 5 |
| 2 | 2 | 2 | 4 | 6 |
| 3 | 3 | 3 | 6 | 3 |
| 4 | 4 | 4 | 8 | 8 |
| 5 | 3 | 3 | 6 | 3 |
| 6 | 4 | 4 | 8 | 5 |
样例里水平倍率是 2，所以同一知识点下的题都会一起乘上 2。
从表里可以看到，原题最后只剩下“若干个物品选不选一次，总时间不能超过 20，总奖励尽量大”这个结构。
思路
先看一个可以直接验证想法的朴素解：
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据暴力解，使用 01 序列枚举每道题做或不做。
const int MAXN = 105;
const int MAXM = 105;
int wky_skill, wang_skill;
int m, n, limit_time;
int topic_time[MAXN]; // 老王做知识点 i 的题需要的时间
int cost[MAXM]; // WKY 做第 i 道题需要的时间
int reward_value[MAXM];
int choose_problem[MAXM]; // choose_problem[i] = 0/1，表示第 i 道题不做/做
int answer;
bool check() {
int used_time = 0;
for (int i = 1; i <= m; i++) {
if (choose_problem[i] == 1) used_time += cost[i];
}
return used_time <= limit_time;
}
int calc_answer() {
int total_reward = 0;
for (int i = 1; i <= m; i++) {
if (choose_problem[i] == 1) total_reward += reward_value[i];
}
return total_reward;
}
void dfs_choose(int dep) {
if (dep == m + 1) {
if (check()) {
int value = calc_answer();
if (answer < value) answer = value;
}
return;
}
// 第 dep 道题的 01 选择：0 不做，1 做。
for (int i = 0; i <= 1; i++) {
choose_problem[dep] = i;
dfs_choose(dep + 1);
}
}
void read_input() {
cin >> wky_skill >> wang_skill;
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> topic_time[i];
}
int ratio = wang_skill / wky_skill;
for (int i = 1; i <= m; i++) {
int p, q;
cin >> p >> q;
cost[i] = topic_time[p] * ratio;
reward_value[i] = q;
}
cin >> limit_time;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
dfs_choose(1);
cout << answer << '\n';
return 0;
}brute.cpp 把每道题看成一个 01 选择：choose_problem[i] = 0/1 表示不做或做。递归先生成完整选择，叶子节点再检查总时间是否超限，并统计总奖励。
这个做法显然正确，但复杂度是
关键观察有三件事：
- 每道题最多只能做一次，所以每题只有“选 / 不选”两种决策。
- 同一知识点下的题，对 WKY 来说耗时完全一样。
- 奖励值和知识点无关，因此每道题都可以独立看成一个物品。
于是把第 i 道题翻译成一个 0/1 物品：
- 重量：
cost[i] = topic_time[p] * (wang_skill / wky_skill) - 价值：
reward[i]
接下来就是标准一维 0/1 背包。
这张表说明 DP 状态到底在表示什么：
| 状态 | 含义 |
|---|---|
dp[t] |
总时间不超过 t 时，能够得到的最大奖励值 |
有了这个定义之后，处理一件物品时就只有两种情况：
- 不选它：
dp[t]保持原值 - 选它：从
dp[t - cost[i]]转移过来，再加上这道题的奖励
所以转移是：
dp[t] = max(dp[t], dp[t - cost[i]] + reward[i])
由于每道题只能做一次，时间这一维必须倒序枚举，避免同一题被重复使用。
最后输出 dp[T] 即可。
DP 公式
设
其中
公式解释：每道题最多做一次，耗时是容量消耗，奖励是收益。若选择当前题，就必须从剩余时间 t-cost_i 的最优状态转移过来。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXM = 105;
const int MAXT = 5005;
int wky_skill, wang_skill;
int m, n, limit_time;
int topic_time[MAXN]; // topic_time[i] 表示老王做知识点 i 的题所需时间
int cost[MAXM]; // cost[i] 表示 WKY 做第 i 道题需要的时间
int reward_value[MAXM];
int dp[MAXT]; // dp[t] 表示总时间不超过 t 时的最大奖励值
void read_input() {
cin >> wky_skill >> wang_skill;
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> topic_time[i];
}
int ratio = wang_skill / wky_skill;
for (int i = 1; i <= m; i++) {
int p, q;
cin >> p >> q;
cost[i] = topic_time[p] * ratio;
reward_value[i] = q;
}
cin >> limit_time;
}
void solve() {
for (int i = 1; i <= m; i++) {
// 0/1 背包必须倒序枚举时间，避免一题被重复选择。
for (int t = limit_time; t >= cost[i]; t--) {
dp[t] = max(dp[t], dp[t - cost[i]] + reward_value[i]);
}
}
cout << dp[limit_time] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的关键不是题面背景，而是把它翻译成背包：
- 每道题就是一个只能选一次的物品
- WKY 的耗时由“知识点耗时 × 水平倍率”得到
- 奖励值就是背包价值
以后看到“每个对象最多选一次、总时间或总容量有限、目标是收益最大”这类条件时，就可以优先往一维 0/1 背包上想。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
