最小化最大成本

給定N個作業和M個任務，將K個作業分配給其中K < =（min（M，N））的K個任務，以使K個作業中的max_cost最小化。最小化最大成本

你能幫我解決問題的算法嗎？我曾試過蠻橫的力量，但我不想爲大量輸入工作。我們可以在這裏使用DP嗎？

您沒有定義'max_cost'或任何類型的成本。 –

maxcost是所有K個工作的最大成本。我們必須爲這些K作業找到任務，以便最大程度地減少maxcost –

謝謝我看到了這一點，但我認爲我不能修改它以適應我的目的。 –

我使用Hopcroft-Karp Problem解決了類似的問題。首先在所有任務和工作之間找到成本。現在循環查看所有成本，看看是否存在基數爲K的二分圖。如果存在，那麼成本就是答案。如果不移動到下一個成本，並將附加邊添加到圖中並再次檢查，直到您到達基數爲K的圖。

2014-03-29 04:35:00

您可以通過測試在二分圖中存在大小K的匹配來解決問題「是否有最大成本X的解決方案」，其中節點是作業和任務，並且在作業和任務之間存在邊緣if執行該任務的工作成本最多爲X.您可以使用the Hopcroft-Karp algorithm來表示這是多項式時間。

然後，您可以使用二分查找找到子問題仍然可行的最小X.

2014-02-22 08:13:00

一種可能的方法是通過二分法找出最大成本。

對於給定的最大成本x，當且僅當可以將K作業與K個任務匹配到一個縮減圖中K個任務可能完成的情況下，成本> x的所有邊都被移除。

您可以使用例如Hopcroft-Karp algorithm測量最大二分配匹配的大小來測試此分配是否可行。

2014-02-22 08:13:16

嘿，好回答！ –

我以爲我是安全的，因爲它沒有一個小時的答案，哦以及:) –

謝謝你的方法工作！ –

回答