背包类树形DP-洛谷P2014 [CTSC1997]选课

目录

• 背包类树形DP
• 例题
• 思路
• 代码

注：本文章参考《算法竞赛 进阶指南》（李煜东2018年1月第一版P291~292）,引用文本均摘自该书

背包类树形DP

又称树形有依赖的背包问题。实际上是背包和树形DP结合。除了以“节点编号”作为树形DP的阶段，通常我们也像线性DP一样，吧当前背包的“体积”作为第二维状态。在状态转移时，我们要处理的实际上就是一个分组背包问题。
另外，还可以按照“左儿子右兄弟”的方法，把多叉树转化为二叉树，再进行计算

例题

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

思路

1. 设置一个0号结点，并将其作为 所有k=0的节点 的父节点，从而将森林转化为树
2. 设f[x][t]表示以x为根的子树中选t门课能够获得的最高分,显然，f[x][0]=0
3. 进一步推状态转移方程：设节点x的某个子节点为y，那么显然f[x][t]可以由f[y][ ]推导而来：t个节点中可能存在a(a∈[1,t])个节点在以y为根的子树上，即f[x][t]=max(f[x][t] , f[x][t-a]+f[y][a])。所以，状态转移:

			for(int j = t ; j >= 0 ; j--)
				if(t - j >= 0)
					if(f[x][t] < f[x][t - j] + f[y][j])
						f[x][t] = f[x][t - j] + f[y][j];

代码

//不小心把题目的k和s搞反了，但不影响结果，自己注意点看
#include <iostream>
#include <cstdio>
#include <cstring>
#define nn 310
using namespace std;
int son[nn] , nxt[nn] , head[nn] , id[nn];//链式前向星存子节点
int fa[nn];
inline void push(int s , int f){
	static int top = 1;
	son[top] = s;
	nxt[top] = head[f];
	head[f] = top;
	top++;
}

int f[nn][nn];
int n , m;
int k[nn];
void dp(int x){
	f[x][0] = 0;
	for(int i = head[x] ; i ; i = nxt[i]){
		int y = son[i];
		dp(y);
		//倒序循环当前选课总门数（当前背包体积） 
		for(int t = m ; t >= 0 ; t--)
			//循环更深子树上的选课门数（组内物品）
			//此处使用倒序是为了正确处理组内体积为0的物品，这里不太明白为什么会有体积为0的物品
			for(int j = t ; j >= 0 ; j--)
				if(t - j >= 0)
					if(f[x][t] < f[x][t - j] + f[y][j])
						f[x][t] = f[x][t - j] + f[y][j];
	}
	if(x != 0)//x不为0时，选修x本身只需要占用 一门课，获得相应学分 
		for(int t = m ; t > 0 ; t--)
			f[x][t] = f[x][t - 1] + k[x];
}
int main(){
	cin >> n >> m;
	for(int i = 1 , s ; i <= n ; i++){
		cin >> s >> k[i];
		push(i , s);
	}
	dp(0);
	cout << f[0][m];
	return 0;
}