我有层次聚类树（使用链接）。每个集群在树状图中都有自己的级别，对应于该集群的成本。我有成本为 c1 的 n1 集群、成本为 c2 的 n2 集群和成本为 c3 的 n3 集群的预算。问题是使用预算选择哪个集群来覆盖所有原始项目。和 c1>c2>c3。成本为 c1 的集群显然可以用于 c2 或 c3 集群。
对于只有一个预算类别，解决方案很简单：只需从根开始，然后在每个子树中，当我们低于 c1 时添加它。如果 n1 个类别在子树之前完成，则没有解决方案。
对于两个类别，它也很简单。查找 c1 成本的所有候选者。用 c2 子集群的数量标记它们，并按降序对它们进行排序。选择具有最大标签的 c1 类别。然后选择 c2 集群。
但是对于超过 2 个类别的问题很复杂，因为对 c2 类别的排序不一定会跟踪 c3 预算。