將最大容量爲W的容器裝入n個物品時，最小化容器數量，同時最大限度地減少容器空間浪費？

Question

所以，要打包以不同的權重w_i成具有最大重量容量的W¯¯箱ň項目。

這就像你的通用裝箱問題，但下面的約束使得不同（可能更容易）：

1. 中的項目順序爲W_1，...，w_i，...，w_n和在考慮下一個項目之前，必須先放置該項目。

最後，您還希望儘量減少每個垃圾箱浪費的空間。這是由一個目標函數定義的 - 普通人的一般行爲是這樣的：如果只有小於或等於垃圾箱的5％被浪費，那麼你沒有問題，並且沒有記錄。否則，如果大於5％被浪費，則會被記錄下來，您不希望這樣做。

目標：儘量減少垃圾箱的數量，同時最大限度地減少浪費的空間。 優先考慮的是首先儘量減少箱數。

什麼是最好的算法/方法呢？

---

我不太確定這是不是垃圾包裝的問題變種，但我問它好像它是反正。如果你們知道哪種問題更適合哪種問題，請告訴我。

此外，我想知道所有可能的方法，我可以用來解決這種問題（動態編程或貪婪的方法）。

在解決一些未實現的嘗試：

1. 我試圖將類似於第一擬合算法貪心方法，但它並不總是最佳的解決方案。有時，浪費的空間並不總是最小化，因爲沒有考慮其他組合。 （而那些其他組合的空間浪費更少）
2. 我也考慮過Dijkstra算法的一些變體，只關注最小化浪費的空間。然而，這一次，我發現它並不總是產生最小數目的垃圾箱。

就是這樣。到目前爲止，我只嘗試過貪婪的方法，因爲我希望有一個簡單的方法來解決它。如果沒有，那麼請賜教。即使疼痛我也會接受。謝謝！

編輯： 我只想知道它是否可以用另一種貪婪的方法解決。另外，我想知道我可以搜索和學習的通用問題，以便它可以幫助我解決這個問題。

Answer 1

「先來的物品必須放在考慮下一個物品之前」 - 這意味着你是塞滿的。你所能做的只是猜測。

我想說，當每個物品到達時，首先檢查是否有一個垃圾箱會從> 5％的垃圾到≤5％的垃圾，然後放在那裏，然後檢查是否有垃圾桶適合放在那裏，如果它不適合放在新的垃圾箱裏。

整個標準似乎有點荒唐。爲什麼三個垃圾箱的填充率分別爲96％，94.5％，94.5％，比95％，95％和95％的三個垃圾桶差？基本上這意味着你想要填滿95％以上的垃圾箱，因爲如果你填寫1到100％，可能意味着另一個垃圾箱降到95％以下。這是直到你需要一個新的垃圾桶，因爲你幾乎有5％的差距。