最佳适应算法_从全部空闲区中找出能满足作业要求且大小最小的空闲分区的一种计算方法

最佳适应算法

从全部空闲区中找出能满足作业要求且大小最小的空闲分区的一种计算方法

最佳适应算法是指从全部空闲区中找出能满足作业要求且大小最小的空闲分区的一种计算方法，这种方法能使碎片尽量小。

计算方法

最佳适应算法（Best Fit）：

它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。

Best fit算法等价于装箱问题，举例如下：

装箱问题：有体积为V的箱子N个，体积为Vi的物品M个，求使得物品全部能够装入箱子，箱子数量的最小值。

假设 V=6 N=10，V1，V2，...,V10分别为：3 4 4 3 5 1 2 5 3 1。计算过程如下：

第一步按物品体积降序排序：5 5 4 4 3 3 3 2 1 1

第二步：取未装箱的最大值5装入第一个箱子。

第三步：判断第一个箱子是否已满，不满且剩余空间为1，搜寻剩下体积小于等于1的物品填入箱子1，箱子1填满。

第四步：重复第二，第三步，直到所有物品装入箱子为止，得到箱子数量为6.

6即时本例N的最小值。

参考资料

最新修订时间：2022-09-25 21:13

条目作者

概述

参考资料