algorithm - 从具有 N 个节点的树中以最小成本选择 K 个节点

Question

有一棵有 N 个节点和 N-1 条边的树(使它成为一棵树)。每个节点都有一个权重 W(i)。你如何选择一个大小为 K 个节点但仍包含原始树的根的子树？我必须这样做，以便最大限度地减少选择此“子树”的“成本”，其中成本定义为保留的所有边的权重之和。

我想我以前做过这样的一道题，好像是DP/递归。但是，当每个节点限制为 2 个子节点时，我知道如何处理它。您已经定义了一个函数 cost(n, i)，这意味着保持 i 个节点从节点 n 开始的最小成本。您将在其中一个 child 中从 i = 0 迭代到 n，然后将其余部分交给另一个 child 。但是，由于每个节点都可以拥有无​​限数量的 child ，有什么办法可以解决这个问题吗？

谢谢

Answer 1

对于给定的节点，您想使用其子节点的 cost(n, i) 来计算 cost(n, i)。从 0..K 开始给 child 编号，你就有了另一个动态程序。在第 j 阶段，您希望仅使用子节点 0..j 计算出最佳的成本集 (n, i)。

我一直在考虑编写这样的代码，同时研究机器学习(只是为了好玩，我想编写通过拟合两个 Weka 分类器而不是一个分类器来查找异常的程序)。这符合您的目的吗？