algorithm - 简单、重要的装箱实例

Question

装箱问题是找到最小数量的大小为v的bin，它可以包含所有大小为[s_1, s_2, s_3, ..., s_n]的对象

我正在寻找装箱问题的一个简单、重要的实例。

简单实例是可以用不超过 5 个 bin 解决的实例。

非平凡实例是最佳拟合递减启发式算法无法解决，但可以通过完全搜索解决的实例。

例如，实例 v = 20, objects = [15, 7, 14, 3, 14, 7, 9] 很简单，但不是非微不足道，因为完整的搜索证明最小的 bin 数量是 5:

[[15, 3], [7, 7], [14], [14], [9]]

然而，最佳拟合启发式算法也会产生 5 箱包装:

[[15], [14], [14], [9, 7, 3], [7]]

是否存在简单、重要的装箱实例？

Answer 1

确实存在这样的实例，即:

v = 20, objects = [11, 7, 7, 6, 5, 3, 1]

最佳拟合递减启发式给出:[[11, 7], [7, 6, 5, 1], [3]]

最佳包装是:[[11, 6, 3], [7, 7, 5, 1]]