確定分時度量請求的快速算法

Question

我正在編寫一個程序，它將模擬特定分時度假的成員如何請求他們的公寓。公寓僅適用於全年的某些「事件」，每個事件都有不同的持續時間（以天計）。對於每個活動，都有一些可用的公寓，根據成本（每天的積分）分成幾組。

我們可能還會遇到部分公寓已經出租的情況，因此某些事件可能無法承認某種公寓類型。

現在我想成員根據這一戰略要求公寓：

• 最大化的事件總計天數是首要任務。
• 最大化花費的點數是第二優先級（因此用戶請求儘可能最好的公寓，並且仍然有儘可能多的日子）。
• 請求的公寓的總成本不能超過該用戶的可用積分總量。
• 顯然，如果某一事件沒有更多的給定類型的公寓，用戶不應該要求特定的公寓/事件組合。

我想知道的問題是否類似於這裏所描述的問題：

http://en.wikipedia.org/wiki/Hungarian_algorithm

在於

它（我想）可能到框架此作爲基質問題其中，每個條目都有一個成本與之相關聯。

但是，不同之處在於，對於我的問題，我可以使用同一間公寓進行多個事件 - 一旦它用於一個事件，它就不會被「花費」。此外，每個項目的成本並不是真正的單一維度，因爲每個活動/公寓組合都具有與其相關的天數和許多點 - 兩者都應該最大化（但優先考慮數量的日子）。

作爲一個例子，假設有三種公寓類型，每天花費75,100和125點，以及三個事件，持續時間爲2,10和4天。讓我們進一步說，很多公寓都採取這樣的可用性矩陣如下所示：

    cost 
      75 100 125 
     2 True False True 
days 10 False False True 
     4 True False True 

我們還假設用戶有可用的1250點。在這種情況下，解決方案將是用戶請求125天公寓的10天活動，而不是其他任何活動。

這樣做或許會是一個遞歸算法的蠻力方式：

• 設n是事件的數量，您正在試圖
• 查找事件和公寓的所有組合，並計算最大化天數，然後花費的點數（這將包括n個事件的所有排列，但也包括3個公寓類型可分配給n個事件的方式的數量）的組合。
• 令n = n-1個

這將很快變得勢不可擋時事件數量上升，我想，所以我想知道是否有可能在一個不太昂貴的方式解決這個問題的任何算法？

Answer 1

如果您有權訪問http://en.wikipedia.org/wiki/Integer_programming的圖書館，您可以嘗試將其扔在此處。

即使您只有一個選項的每個事件的成本，以便您只是試圖選擇覆蓋儘可能多的總天數事件的組合，而不超過預算，我認爲這會減少到http://en.wikipedia.org/wiki/Knapsack_problem。這意味着它不可能完全用匈牙利算法等最壞情況的多項式時間算法求解。