加入虚拟根把课程森林变成树，用树形背包维护每个子树选若干课程的最大学分。
OJ: luogu
题目 ID: P2014
难度:普及+/提高
标签:树上背包树形DP动态规划
日期: 2025-12-30 17:17
题意
有 n 门课程，每门课程有学分，并且可能有一门直接先修课。
要选择恰好 m 门课。如果选择某门课，必须先选择它的先修课。求最大总学分。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据暴力解，使用 01 序列枚举每门课程选或不选。
const int MAXN = 25;
int n, m;
int parent_course[MAXN];
int credit[MAXN];
int choose_flag[MAXN]; // choose_flag[i] = 0/1，表示第 i 门课程不选/选
int answer;
int calc_chosen_count() {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (choose_flag[i] == 1) cnt++;
}
return cnt;
}
bool check() {
if (calc_chosen_count() != m) {
return false;
}
for (int i = 1; i <= n; i++) {
if (choose_flag[i] == 1 && parent_course[i] != 0 && choose_flag[parent_course[i]] == 0) {
return false;
}
}
return true;
}
int calc_answer() {
int sum = 0;
for (int i = 1; i <= n; i++) {
if (choose_flag[i] == 1) sum += credit[i];
}
return sum;
}
void dfs_choose(int dep) {
if (dep == n + 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_flag[dep] = i;
dfs_choose(dep + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> parent_course[i] >> credit[i];
}
answer = 0;
dfs_choose(1);
cout << answer << '\n';
return 0;
}brute.cpp 把每门课程看成一个 01 选择：choose_flag[i] = 0/1 表示不选或选。递归先生成完整选择，叶子节点再检查是否恰好选了 m 门课、先修课是否都满足，并统计总学分。
课程依赖可能是一片森林。为了统一处理，加入一个学分为 0 的虚拟根 0，让所有没有先修课的课程都成为它的孩子。
这样原问题变成：在以 0 为根的树中选 m+1 个节点，并且必须选根 0。
定义：
text
dp[u][j] = 在 u 的子树中选 j 门课，并且必须选 u，能得到的最大学分初始化：
text
dp[u][1] = credit[u]处理一个孩子 v 时，把名额分给 v 的子树：
text
dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k])这里的 k 表示从孩子 v 的子树中选多少门课。每个孩子子树相当于一组物品，合并过程就是树上的分组背包。
最终答案：
text
dp[0][m+1]代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
const int NEG = -1000000000;
int n, m;
int credit[MAXN];
vector<int> children[MAXN];
int dp[MAXN][MAXN]; // dp[u][j]：在 u 的子树中选 j 门课，并且必须选 u，能得到的最大学分。
void read_input() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int parent;
cin >> parent >> credit[i];
children[parent].push_back(i);
}
}
void dfs(int u) {
for (int j = 0; j <= m + 1; j++) {
dp[u][j] = NEG;
}
// 若选择 u，至少占用 1 个名额。虚拟根 0 的学分为 0。
dp[u][1] = credit[u];
for (int idx = 0; idx < (int)children[u].size(); idx++) {
int v = children[u][idx];
dfs(v);
// 树上背包：把总名额 j 分一部分 k 给孩子 v 的子树。
for (int j = m + 1; j >= 1; j--) {
for (int k = 1; k < j; k++) {
if (dp[u][j - k] == NEG || dp[v][k] == NEG) {
continue;
}
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
}
}
}
}
void solve() {
dfs(0);
cout << dp[0][m + 1] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
时间复杂度约为
总结
树上背包的关键是把“每个孩子子树选多少个”看成容量分配。
虚拟根能把森林问题统一成一棵树，避免对多个根单独处理。