「填充」樹的算法

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）。這些邊緣的吞吐量是資源的數量。然後，將所有樹木連接到資源。您修改您的樹，以便節點吞吐量達到傳出邊緣吞吐量 然後，您的樹的輸出將轉到一個目標節點。