web analytics

树形依赖背包裸题

题目:有一个树,每一个节点代表一个物品,每个物品有重量和价值,每个物品必须先选父亲才能选自己。求给定重量内最大价值。

分析:

先求出DFS序。

然后从叶子节点开始(DFS序后面)往前。

每个点有两个决策,选这棵子树。或者是不选这棵子树。

 

Post a Comment

You must be logged in to post a comment.