考慮到與最大權重的電梯和n與X_I權的人，找出需要乘坐的最小數量

input: 
max_weight = 550 
n = 4 
x_i = [120, 175, 250, 150] 

output: 
2 
// [[250, 175, 120], [150]]

我的初步印象是，這看起來非常相似，動態規劃硬幣找零/揹包問題，但它不是硬幣改變（這會要求最少數量的權重來確定一個數量），而不是揹包（權重沒有值，它就像我可以有超過1個揹包）。考慮到與最大權重的電梯和n與X_I權的人，找出需要乘坐的最小數量

這個問題是否有一個共同的名稱/解決方案？

來源

2017-08-08 kayla

在我看來，這是簡單的bin包裝 –

這實際上是一個(1D) Bin Packing problem：

在裝箱問題，不同體積的對象必須被打包到有限數目的二進制位的或容器的方式的每個卷第V最小化使用的垃圾箱數量。在計算複雜性理論中，它是一個組合NP難題。

這裏的人物映射在遊樂設施的箱子上。像垃圾箱包裝問題一樣，我們希望儘量減少「使用」遊樂設施的數量，並且每個人都佔用一定的「體積」（即該人的體重）。

裝箱問題是 - 正如文章中所述 - NP-hard。我們可以使用動態編程（但它仍然有 - 最壞的情況 - 指數時間）。

The paper A New Algorithm for Optimal Bin Packing by Richard E. Korf討論了一種準確解決這個問題的算法。它的工作原理是首先使用啓發式方法並計算下限，然後使用分支和邊界迭代地導出比啓發式方法更好的解決方案，直到達到下限或者再也找不到解決方案。

來源

2017-08-08 19:28:53

請糾正我，如果我錯了（不是最有效的），但我認爲你可以把所有的權重到max heap，然後使用greedy algorithm來挑選集。

來源

2017-08-08 16:40:42

是的，假設個人的順序沒有什麼區別，（誰先到達電梯），那麼我必須同意Sritej，這看起來像一個貪婪的算法給我...我相信它也是最高效的 – brw59

假設權重限制爲7，並且人員權重爲[3，3，2，2，2，2]。那麼最佳答案是2，但是你的算法給出了3. – ruakh

@ruakh你是對的。由於這些類型的情況，貪婪算法會失敗很多時間=/ –

你在正確的軌道上。這個問題可以通過修改硬幣更換算法來解決：不是要求精確的解決方案，而是找到一個達到最高總量而不超過目標數量的問題。當然，如果你發現一個解決方案的缺陷少於任何剩餘的集合元素，你就停下來報告解決方案。

當您找到解決方案時，請刪除「已使用」的權重並迭代，直到您將它們全部分配爲止。迭代次數是您需要的電梯數量。

如果按降序對元素進行排序，這會給你一個以回溯開始的「貪婪」。我懷疑這在很多情況下是相當接近最優的，特別是如果你記錄結果，以免在下一次迭代中重複出現錯誤。

你可以嘗試一些病理情況下，如100的限制，和極端的重量比如

[93, 91, ..., 5, 4, 4]

的「貪婪」算法進行了93 + 5首，但後來平息了91 + 4 + 4 （更近的解決方案）。這是備忘錄派上用場的地方。

這是否讓您朝着解決方案邁進？

來源

2017-08-08 17:03:20 Prune

在某些情況下，這可能會給出錯誤的答案。假設權重限制爲14，人員權重爲[10,6,6,6,6,3,2,2]。那麼正確答案是3（10 + 3,6 + 6 + 2,6 + 6 + 2），但是你的方法可以給出4（10 + 2 + 2,6 + 6,6 + 6，3）。 – ruakh

不錯的測試！這*會*在這種情況下給出錯誤的答案。問題就出現在你構建它的時候：當這些小值對於找到比「最大的第一個」排序所能獲得的更多的「中值」最大解決方案至關重要時。 – Prune

考慮到與最大權重的電梯和n與X_I權的人，找出需要乘坐的最小數量

回答

相關問題