“填充”树的算法

Question

我正在寻找最佳方式来填充由一系列树和数据图所描绘的要求。一个基本的树可能是这样的：

10 
/\ 
A B 

而且地图数据的可能是这样的：

A: 7 
B: 6 

在这些例子中，10代表的要求，而数据表是我跟...共事。所以，我可以给它4 A秒和6个B S，或每5等，现在“补”这棵树，我想用所有的A S和B的可用给我，并具有盈余ISN”这肯定是一个问题（所以我打算在这种情况下给7和6），但事情变得更加复杂;我们可以有多种树木，树木可以有多个级别，其中每个节点，但叶子的要求，可能给我们这样的事：

 40       30 
/ | \     /\ 
    20 C D     A C 
/\ 
A B 

所以，我们需要的A和B在第一棵树添加20，在第一棵树的C和D添加到二十个，并在第二树A和C添加到30（无树应该有两次出现相同的字母）。我们可以在任何数量的级别一棵树，或任何数量的树。

最后，我们的数据可能不是完美的。在优化后可能无法完全填满两棵树（我们可能会有两棵树不满足要求，我们可能会有一棵树超过要求，另一棵树可能不足）等等。我需要的是一种鉴于这些树，有多少A S，B S，C S，等我们有可用的列表，填补了许多树木越好。我们已经有一段时间了，但我们没有一个证据足以证明“这种方式每次都有效”。

有谁知道的方式做到这一点？

Answer 1

它是最大流量问题。 https://en.wikipedia.org/wiki/Maximum_flow_problem
但您需要修改图形。 你有一个来源。源通过边缘连接到您的资源（A，B，C）。这些边缘的吞吐量是资源的数量。然后，将所有树木连接到资源。您修改您的树，以便节点吞吐量达到传出边缘吞吐量 然后，您的树的输出将转到一个目标节点。