二部圖 - 賣方和買方

鑑於多個賣方和買方，每個賣方都有一定數量的產品，每個買方想從賣方購買多個產品。有些賣家不能與一些買家進行交易，如果買家無法獲得足夠的產品，交易就不會成功。如果我們知道有一種策略可以滿足所有買家，那麼如何找到這種策略呢？二部圖 - 賣方和買方

我畫了一張圖來說明問題，這只是一個例子。該問題希望您爲每個買方提供交易策略，以便所有買方都能獲得他們想要的足夠多的產品。 seller buyer example

來源

2017-01-09 AvocadoAushi

我假設一個買家可以從一個賣家購買多件東西。將它改爲一個項目並不難。

這可以通過最大流算法來解決。直接從買方到其連接的賣方。爲這些邊分配容量b_i。 B_i是買方需要的金額。添加兩個節點S，T。從S向所有買家添加邊緣。將容量b_i分配給每個邊。 B_i又是我需要的買家的金額。將每個賣方頂點的邊添加到T.將容量S_i分配給這些邊。 S_i是賣方的金額。找到從S到T的最大流量。如果它等於所有買家所需金額的總和，那麼就有問題的解決方案，並且可以通過從買方到賣方的每個邊緣的流量來找到（這是積分流動定理的後續）。

來源

2017-01-09 23:42:40

嗨，Saeed，非常感謝你的出色解決方案。抱歉，我沒有清楚地描述問題。最初，您不知道是否所有買家都能滿意，並且您被要求儘可能多地滿足買家，並且每個買家都可以從多個賣家處購買產品。你的解決方案非常好，但是如果你將邊緣容量設置爲s_i，以滿足賣家i的所有邊緣，賣家i的總數可能會超出，對嗎？ – AvocadoAushi

既然你不能滿足一個買家的產品比他的要求低，如果我使用最大流量理論，即使我可以得到最大流量，但我仍然無法獲得滿意買家的數量（如果我們不知道所有的買家都可以得到滿足，我們希望找到滿意的買家的最大數量）。 – AvocadoAushi

@AvocadoAushi，1.賣家總數不會超過S_i，因爲它的外向邊有容量S_i，不能攜帶更多流量。我回答了你問的問題。你現在解釋的是不同的情況，但我會考慮這個問題，你可以把它變成一個新的問題。 –

二部圖 - 賣方和買方

回答

相關問題