包裝重量

Question

如果我有一些項目少於一磅，我想有效地將​​它們裝入一個一磅的集裝箱，我應該通過蠻力這樣做嗎？ （找出所有各種組合，包裝，並查看哪些組合導致最小數量的包裝？）

是否有這種算法的名稱？

在我的情況下，我沒有大量的軟件包。

Answer 1

我寫了下面的Ruby程序來解決這個問題，看起來效果很好。

https://gist.github.com/1398026

Answer 2

你可能想看看knapsack problem

Answer 3

你也可以找一維裝箱或2D裝箱算法。如果你沒有太多垃圾箱，我建議使用暴力破解算法，但它似乎是一個非常困難的問題。

Answer 4

這是NP完整的問題。你沒有更好的選擇，最好的可能是一些具有僞多項式（指數）複雜度的動態規劃算法。

Answer 5

你可以看看算法設計手冊您的問題的描述：

裝箱 http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

揹包問題 http://www.cs.sunysb.edu/~algorith/files/knapsack.shtml

你或許可以更容易上你自己如果你可以定義一個適合的解決方案（足夠好），而不是如果你想知道最好的解。