求助树上 dp 第二维枚举顺序

树上 dp 典题：

有一棵 $n$ 个点， $n-1$ 条边的树，每个节点有重量 $w_i$ 和价值 $v_i$ ，背包重量为 $m$ ，求总重量不超过 $m$ 的情况下，最大的价值。一个节点可以选，当且仅当它的父节点被选中。

$n,m \le 2000$

写了一个

O(nm^2)

的暴力 dp，但是有个问题：

（

\text{dp}_{i,j}

表示以

i

为根的子树中当前背包容量为

j

时的最大价值）。

CPP

void dfs(int u, int fa) {
	F(i,w[u],m) dp[u][i]=v[u];
	forGraph(u){
		int t=G[i].to;
		if(t==fa) continue;
		dfs(t,u);
		for(int j=m; j>=w[u]; j--) { // here
			for(int k=0; k<=j-w[u]; k++){
				dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[t][k]);
			}
		}
	}
}

在 here 一行中，为什么背包的容量只能倒序枚举，而不能正序枚举。

如需要完整代码见此。

如有解答请 @ 我，谢谢大家。

求助树上 dp 第二维枚举顺序

讨论操作

回复

相关推荐

求助树上 dp 第二维枚举顺序