平等排空處理算法

Question

我正在處理類似於Bin packing problem的問題。

問題

我有幾個垃圾箱。每個箱包含幾個具有相同重量的物品（例如1,2,5,10公斤）。每個垃圾箱中的物品數量是不同的。爲了達到一定的重量，我必須實施一種算法來計算應該分配的物品的數量，以便在更多操作的過程中，箱體幾乎同時是空的。

例

1. B1具有50項與重量1公斤
2. B2具有90項與重量2千克
3. B3具有80項與5千克
重量
4. B4具有50項爲10重量公斤

算法應計算NU許多應該處理的物品達到45公斤。該算法應返回類似於以下結果： 10 * B1 + 3 * B3 + 1 * B4 = 45 Kg。

我想知道是否有任何已知的算法可以用來解決我的問題。我已經有了一個算法，它可以計算所需的所有排列，以便分配預期重量所需的項目，但是我有問題需要弄清楚，應該根據每個垃圾箱中物品的可用性來選擇哪種排列方式。

Answer 1

通過首先考慮只包含比最小垃圾箱多的物品的垃圾箱，您可以將問題分解爲一系列大小相等的垃圾箱包裝問題，然後重複該操作，直到所有垃圾箱具有相同的尺寸。

因此，使用已知的（維基百科文章）bin裝箱算法對上述減少的箱子集合。

Answer 2

我不認爲bin裝箱算法它是我的問題的最佳解決方案。我實現了最適合的裝箱算法。首先，我根據可用項目對數據進行降序排序。我遍歷所有項目，直到我有解決方案或項目列表爲空（未找到解決方案）。對於下面的情況下，算法沒有找到一個有效的解決方案：

• B1 40項與配重與配重100
• B2 30項50
• B3 20項與配重20

對於權重350，該算法找不到任何有效結果。

結果1（340）100 50 20 100 50 20 結果2（340）100 50 20 100 50 20 .....