洛谷题单指南-树与图上的动态规划-P2014 [CTSC1997] 选课

原题链接：https://www.luogu.com.cn/problem/P2014

题意解读：课程之间有的有依赖，有的可以直接选，问选不超过m个课程的最大学分和。

解题思路：

对于没有依赖的课程，假定一个课程0，设依赖课程0，课程0必选，且学分为0。

这样一来，要选择不超过m个课程则变成选m + 1个课程。

接下来，就采用有依赖的背包问题求解。

1、状态表示

设f[i][j]表示在以i为根的子树中选不超过j门课的最大学分和

2、状态转移

将每一个子树看做分组

从大到小枚举背包体积，即选择的节点数

在每一个分组中枚举所有的物品，每一个物品就是在分组中选择所有少于背包体积的节点数

f[u][i] = max(f[u][i], f[v][j] + f[u][i - j]);

3、初始化

根节点u是必选的，f[u][1~m] = w[u]

4、结果

f[0][m]

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 305;
vector<int> g[N];
int w[N];
int f[N][N]; //f[i][j]表示在以i为根的子树中选不超过j门课的最大学分和
int n, m;

void dfs(int u)
{
    for(int i = 1; i <= m; i++) f[u][i] = w[u]; //初始化，u必选
    for(int v : g[u])
    {
        dfs(v);

        for(int i = m; i >= 0; i--) 
            for(int j = 0; j < i; j++) //子树分组选择的数量比体积小1，给根节点留一个位置
                f[u][i] = max(f[u][i], f[v][j] + f[u][i - j]);
    }
}

int main()
{
    cin >> n >> m;
    m++; //根节点0必选，容量增加一个
    for(int i = 1; i <= n; i++)
    {
        int k, s;
        cin >> k >> s;
        g[k].push_back(i);
        w[i] = s;
    }
    dfs(0);
    cout << f[0][m];
    return 0;
}