最小消息长度算法

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连锁。忽略蛮力或分支和绑定：它们不会超出玩具问题。