最佳解決方案 - 規劃理論

我希望有人來解釋不同的方法，以一個簡單的問題，然後我會在PHP嘗試和實現它的廣泛應用。最佳解決方案 - 規劃理論

我有五個人誰選擇誰有什麼房間有五個房間盛大，大，中，中，小。

Person 1 orders the rooms Grand, Large 
Person 2 orders the rooms Large, Medium 
Person 3 orders the rooms Large, Small 
Person 4 orders the room Medium 
Person 5 orders the rooms Large, Medium

如果丟失的房間是他們不感興趣的

什麼是選擇誰得到每個房間最公平的做法？

來源

2012-05-14 Pez Cuckow

如果你可以假設每個人總是可以有一個他們選擇的房間（例如，他們並不都選擇「中等」），你應該按照他們想要的房間的升序來處理。在這種情況下，第4人有優先權，然後你清除所有其他人的名單中的媒體選擇，重複。 – MarioDS

公平並不總是很好的定義。

但是，在這種情況下，似乎一個人可以得到他要求的房間，或者沒有。因此，人們可以強有力地爭辯說，相同數量的人獲得他們想要的房間的所有解決方案同樣公平，並且更多人獲得他們想要的房間的解決方案比那些獲得他們想要的房間更公平（我們是因此不給任何一個人偏好）。

在您的例子似乎只有一個解決方案，每個人都得到他想要的房間。因此，這是「最公平的」解決方案。

找到這個算法的算法只是一個深度優先搜索（或者，如果您需要加速的話，分支和界限），它會考慮所有可能的分配並找到最大分配。

來源

2012-05-14 17:47:04

使用啓發式算法來計算的每一種情況的匹配值。例如。如果一個人沒有房間，價值會很低或者是負值。如果每個人都保持着他們訂購的最大房間，價值將是最高的。

計算每一種情況這個值，然後取最高值的情況。

來源

2012-05-14 13:12:15 Sjoerd

最佳解決方案 - 規劃理論

回答

相關問題