儘量減少只有兩名工人的任務成本

我正在嘗試使用PHP創建一個算法，通過選擇兩名可以儘可能便宜地完成這些任務的工作人員來找出完成一組任務的最佳方法。儘量減少只有兩名工人的任務成本

假設我有一組X個不同的任務和Y個不同的工作人員。每個工作人員可以完成每個X任務的不同價格。您可以假設我有一張表格，顯示每個工作人員和每個任務的工作人員完成任務所需的價格。

我的問題是這樣的：給定這樣一個表格，我如何找到一套正好兩個工人誰可以完成所有的任務以最小的總成本？

來源

2011-08-19 Caleb Welty

這似乎或多或少像最短路徑問題。 – Mahesh

那麼到目前爲止你想出了什麼？對我來說似乎是一個家庭作業類型的問題 - 在學校裏就像這樣做。而且，首先通過自己的解決方案並**，然後**提出問題，這是非常有價值的。 #justsayin – itsmatt

到目前爲止，我唯一的解決方案是templatetypedef提出的同一個解決方案。 –

這是一個可以使用dynamic programming方法解決的優化問題。您的特殊問題（我相信）屬於resource allocation的財務限制。標準問題如knapsack problem也包括在內。

在堆棧溢出中至少有一個question要求使用php解決這些問題。在那篇文章中，有一個關於揹包問題的php解決方案的鏈接。我會從that code開始，並將其變爲您需要掌握的特定問題定義。

來源

2011-08-19 02:15:10 unclejamil

不錯的鏈接！我會看看，看看它會如何幫助。 –

解決這個問題的一個非常簡單的方法是考慮所有可能的兩名工人對，然後計算成本，如果這兩名工人將所有工作分配到最佳狀態。一旦你有了這些價值觀，你可以把它們中最小的一個拿到整體最小的成本。

現在，讓我們看看如果計算完成所有X任務的總成本（如果您要使用特定的一對工作人員）。從你的問題描述來看，似乎每個工人都沒有限制他們能做多少工作，這使得這個問題比許多相關問題要容易得多。直覺是這樣的：對於任何任務，你都想把這個任務交給工作人員，而這個工作可以比另一個更便宜。因此，可以通過循環每個任務來找到分攤兩個工人之間所有任務的總成本，然後將該任務分配給可以以較少資金完成任務的工人。總的來說，我建議接近這個問題如下。使用double for循環，遍歷每一對工人。對於每一對，使用第三個for循環遍歷每個任務，計算完成該任務的總成本。最後，如果這一對比迄今爲止最知名的一對好，那麼更新你的猜測就是這個特定的對。一旦你對每一對工作人員運行這個循環，你就會發現這對能以最低的總價格做到這一點。

由於爲O（Y ）對工人和X總的任務，這將在O的（Y X）的時間。

希望這會有所幫助！

來源

2011-08-19 07:44:22 templatetypedef

所以這也是我最初的解決方案，但似乎應該有一種解決問題的更有效的方法。 –

儘量減少只有兩名工人的任務成本

回答

相關問題