最小消息長度算法

Question

我有對象的不同尺寸的束（很多的對象可以具有相同的尺寸，例如：我有6B的54目的，10B的76，24B等的79

的對象的大小是6,8,10 ......字節）。我需要將這個包打包成幾條消息（每條消息的最大長度爲256字節）。

問題是如何使用最少數量的消息獲得解決方案？

是否有任何已知的算法呢？我需要Hopfield神經網絡嗎？

Answer 1

這是一個bin packing problem這是一個組合NP難題的例子。最簡單的算法是「First Fit Decreasing（FFD）」，您首先通過減小大小來排序對象，然後將每個對象插入列表中的第一條消息，並留下足夠的空間。

Answer 2

這是一種揹包問題，但不是的揹包問題。這是Bin packing problem，其中不同卷的項目打包到最小數量的箱子中，這些箱子都是相同的大小。這是NP難。

Answer 3

該第一適合減少（FFD）算法不是最佳的（但一個非常好的開始）。如果您有更多的執行時間和更多的開發時間，與simulated annealing，禁忌搜索或遺傳算法 IT連鎖。忽略蠻力或分支和綁定：它們不會超出玩具問題。