我有不同大小的对象包（很多对象可以具有相同的大小，例如：我有 54 个 6B 的对象、76 个 10B 的对象、79 个 24B 的对象等。
对象的大小为 6, 8 ,10 .... 字节）。我需要将该捆绑包打包成几条消息（每条消息的最大长度为 256 字节）。
问题是如何以最少的消息获得解决方案？
有什么已知的算法吗？我需要 Hopfield 神经网络吗？
问问题
243 次
3 回答
3
这是装箱问题的一个例子，它是一个组合 NP 难题。最简单的算法是“First Fit Decreasing (FFD)”，您首先通过减小大小对对象进行排序，然后将每个对象插入到列表中具有足够剩余空间的第一条消息中。
于 2011-01-26T18:13:50.993 回答
1
这是一种背包问题，但不是背包问题。这是Bin 打包问题，其中不同体积的物品被打包到最小数量的 bin 中，这些 bin 的大小都相同。这是NP难的。
于 2011-01-26T18:14:02.810 回答
0
第一次拟合递减 (FFD)算法不是最优的（但一个很好的开始）。如果您有更多的执行时间和更多的开发时间，可以将其与模拟退火、禁忌搜索或遗传算法联系起来。忽略蛮力或分支和约束：它们不会超出玩具问题的范围。
于 2011-01-27T07:49:11.720 回答