使用一维装箱算法优化工作分配_2.算法(2)

2.6。按项目大小应用降序排序

到目前为止，我们已经了解了Next Fit、First Fit、Worst Fit、Best Fit各个算法的运行方法和执行结果。当输入数据的大小没有按一定顺序排列时以随机顺序处理和以排序状态处理的结果是不同的。由于先填充大尺寸的项目通常会产生良好的效果，因此您可以考虑先按降序对项目进行排序，然后再进行处理的方法。

首先，输入数据和按降序排序的数据如下。

# 输入数据 26 57 18 8 45 16 22 29 5 11 8 27 54 13 17 21 63 14 16 45 6 32 57 24 18 27 54 35 12 43 36 72 14 28 3 11 46 27 42 59 26 41 15 41 68

# 按降序排序 输入数据 72 68 63 59 57 57 54 54 46 45 45 43 42 41 41 36 35 32 29 28 27 27 27 26 26 24 22 21 18 18 17 16 16 15 14 14 1 3 12 11 11 8 8 6 5 3

让我们看一下以降序排序的数据作为输入运行每个算法的结果。

2.7.下一个适合降序排序

总空间为1,840（每个bin的大小80 * bin的数量23），剩余空间总计为488，空间低效约为26.52%（488/1,840）。

2.8.首次拟合降序排序

总空间为1,440（每个bin的大小80 * bin的数量18），总剩余空间为88，空间低效约为6.11%（88/1,440）。

2.9.最差拟合降序排序

总空间为1,440（每个bin的大小80 * bin的数量18），总剩余空间为88，空间低效约为6.11%（88/1,440）。

2.10.最适合降序排序

总空间为1,440（每个bin的大小80 * bin的数量18），总剩余空间为88，空间低效约为6.11%（88/1,440）。

2.11.算法应用结果对比

 在上面考察的案例中，除了无效率最大的 Next Fit 外，First Fit、Worst Fit 和 Best Fit 的剩余空间总和和空间无效率的结果都是相同的，并且每个 bin 中填充的项目为配置不同。

作为参考，相同的结果是由本示例中的输入数据和约束引起的重合。如果输入数据和约束不同，则剩余空间总和、空间低效率、箱的项目组成列表等可能不同。

未排序和排序结果的比较如下。

▼ 下一个适合

▼ 首次适配

▼ 最差拟合

▼ 最适合

以下是每个算法执行时产生的定量信息。

算法	物品	排序前	排序后	比较
下一次适合	比较次数	44	44	不用找了
	整体空间	1,840	1,840
	剩余空间总和	488	488
	空间效率低下	26.525	26.525
首次适配	比较次数	330	448	比较次数增加，但空间效率低下现象减少并得到改善
	整体空间	1,520	1,440
	剩余空间总和	168	88
	空间效率低下	11.05%	6.11%
最差拟合	比较次数	465	643
	整体空间	1,680	1,440
	剩余空间总和	328	88
	空间效率低下	19.52%	6.11%
最合适	比较次数	428	643
	整体空间	1,520	1,440
	剩余空间总和	168	88
	空间效率低下	11.05%	6.11%

上表中的比较次数是基于Excel VBA的工具的近似测量，接下来将介绍该工具。从上图可以看出，按物品大小降序排序后的 Bin Packing 结果降低了空间效率，并且包装更加密集。由此可见，先排序再应用算法可以获得更加优化的结果。

最适合并不总是最佳的。建议检查每个算法运行的结果并选择适合当时情况的最佳结果。

---

到目前为止，我们已经详细了解了 Bin Packing 算法。接下来，我们看看实现该算法的工具。

---

<< 相关文章列表 >>

• 使用一维装箱算法优化工作分配_1.概述
• 使用一维装箱算法优化工作分配_2.算法（一）
• 使用一维装箱算法优化工作分配_2.算法(2)
• 使用一维装箱算法优化工作分配_3.实现（一）
• 使用一维装箱算法优化工作分配_3.实现（二）
• 使用一维装箱算法优化工作分配_4.附件
• 一维装箱工具近期变化（截至 2021 年 3 月 21 日）
• 使用一维装箱算法的工作分配优化工具 全文, 下载