算法简介:贪婪算法----近似装箱问题
算法简介
近似装箱问题
设给定N项物品,大小为s1，s2，…，sM,所有的大小都满足0<s1≤1.问题是要把这些物品装到最小数目的箱子中去,已知每个箱子的容量是1个单位.作为例子,下图所示为把大小为0.2，0.5，0.4，0.7，0.1，0.3，0.8的一列物品最优装箱的方法.
解决算法
- 请注意:既然采用的是贪婪算法解决近似装箱问题,所得的接不一定是最优解,但是离最优解不太远
联机算法
1. 下项适合算法
- 算法思路
当处理任何一项物品时,我们检查看它是否还能装进刚刚装进物品的同一个箱子中去.如果能够装进去,那么就把它放入该箱中;否则,就开辟一个新的箱子将其放进去. - 算法特点
令M是将一列物品Ⅰ装箱所需的最优装箱数,则下项适合算法所用箱子数绝不超过2M.存在一些顺序使得下项适合算法用箱2M-2个. - 算法图解
2. 首项适合算法
- 算法思路
算法的策略是依序扫描这些箱子,并把新的一项物品放入足能盛下它的第一个箱子中.因此,只有当前面那些放置物品的箱子都容不下当前物品的时候,我们才开辟一个新箱子. - 算法特点
- 令M是将一列物品Ⅰ装箱所需要的最优箱子数,则首次适合算法使用的箱子数绝不多于17/10M+7/10,存在使得首次适合算法使用17/10(M-1)个箱子的序列.
- 当首次适合算法对大量其大小均匀分布在0和1之间的物品进行运作时,经验结果指出,首次适合算法用到大约比最优装箱方法多2%的箱子.在许多情况下,这是完全可以接受的.
- 时间复杂度
O(NlogN) - 算法图解
3. 最佳适合算法
- 算法思路
该算法不是把一项新物品放入所发现的第一个能够容纳它的箱子,而是放到所有箱子中能够容纳它的最满的箱子中. - 算法特点
该算法绝不会超过最优算法的大约1.7倍 - 时间复杂度
O(NlogN) - 算法图解
脱机算法
- 所有联机算法的主要问题在于将大项物品装箱困难,特别是当它们在输入的后期出现时.围绕这个问题的自然方法是将各项物品排序,把最大的物品放在最先.此时可以应用首次适合算法或最佳适合算法,分别得到首次适合递减算法和最佳适合递减算法.
1. 首次适合递减算法
- 算法思路
将所有数据进行降序排序,然后采用首次适合算法 - 算法特点
如果一种最优装箱法使用M个箱子,那么首次适合递减算法使用的箱子数绝不超过(4M+1)/3个 - 算法图解
2. 最佳适合递减算法
- 算法思路
将所有数据进行降序排序,然后采用最佳适合算法