0
最近，我遇到了一個真正的問題，我可以refolmulate爲以下算法任務的錢給量：是否有可能與給定的成本出售的所有項目，以人
問題：
給定一組N個人，每個人都有一定數額的金錢和一套M物品，每個物品都有一定的成本，是否有可能出售所有物品？
每件商品最多隻能由一個人購買，每個人可以購買多件商品，以使其成本不超過他所擁有的金額。
我嘗試的解決方案：
我想構建一個網絡，找到一個最大流這樣的方向：
- 使對應於人的一部分與頂點的bipartide圖，而在其他部分 - 項目。
- 將人連接到源S，並將邊緣容量設置爲人們擁有的金錢。
- 將物品連接到水槽T並將邊緣能力設置爲物料成本。
- 連接每個人的項目，他可以購買和設置邊緣能力的項目成本
在情況下，在最大流量每邊在這個網絡中發現要麼是空的或完全飽和的，這個問題將通過尋找可以解決如果所有到T的邊都是飽和的，並且如果我們想知道誰應該買什麼物品，我們會看左邊和右邊部分之間的邊緣。
但是，問題是，產生的流可以包含部分填充的邊緣（意思是一個人部分支付一些項目），這種情況下，我無法消除。