histcat

Title#

[CTSC1997] Course Selection#

Problem Description#

In university, every student must select some courses from many available in order to achieve a certain number of credits. Some courses must be taken before others; for example, advanced mathematics must always be taken before other courses. Now there are $N$ courses, each with a certain number of credits, and each course may have one or no direct prerequisites (if course a is a prerequisite for course b, then course b can only be taken after completing course a). A student needs to choose $M$ courses from these, and the question is how many maximum credits can they obtain?

$1 \leq N \leq 300$, $1 \leq M \leq 300$

Solution#

Tree DP + Knapsack

Let f[u][i][j] represent the maximum credits obtainable by selecting j courses from the first i courses in the subtree rooted at u.

It turns out this is similar to the 0/1 knapsack problem, except we need to enumerate how many courses to select from each subtree of u (what j is).

We can use a rolling array and reverse loop to reduce the space to one dimension.

Problem#

The number of courses selected from the subtree cannot equal q; otherwise, the root of this subtree cannot be selected, leading to the inability to select all courses in the descendants (line 48).

Code#

#include<bits/stdc++.h>

using namespace std;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

const int N = 310;

int n, m;

int s[N], size[N];

int head[N], nxt[N], to[N], cnt = 1;

int f[N][N];// Represents the maximum credits obtainable by selecting m subjects from the subtree rooted at u

void add(int x, int y)
{
	nxt[++cnt] = head[x];
	to[cnt] = y;
	head[x] = cnt;
}

void dfs(int u)
{
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		dfs(v);
		for(int q = m;q >= 0;q--)
		{
			for(int k = 0;k < q/* The number of courses selected from the subtree cannot equal q; otherwise, the root of this subtree cannot be selected, leading to the inability to select all courses in the descendants */;k++)
			{
				f[u][q] = max(f[u][q], f[v][k] + f[u][q - k]);
			}
		}
	}
}

int main()
{
	n = read(), m = read() + 1;

	int anc;

	for(int i = 1;i <= n;i++)
	{
		anc = read();
		s[i] = read();
		add(anc, i);
		f[i][1] = s[i];
	}
	dfs(0);
	cout << f[0][m];
}