A-A+

装箱问题的几种算法

2017年06月06日 算法 暂无评论

一种箱子的装箱问题

装箱问题描述

简单说就是有一组体积为v1,v2……vn的不可拆分打货品,要放入容量为V的g箱子中,怎样才能让箱子最少。

这个问题据说研究了好几百年,没有一个完美的方案,没法得到全局最优解,只能得到近似最优解。

NF/NFD 算法

NF(Next Fit) 即下次适应算法 , 是对输入序列 L 中的物品 a 填充一只箱子 ,物体放入正在填装的箱子直到下一个物品放不下为止 , 然后考虑开启新的箱子安置物品 , 且不再有物品放入早先考虑的箱子里。因 NF算法处理每个物品只检查一个箱子 , 其时间复杂性是线性的 , 这种特性使得前面箱子剩余空间再无利用的可能 。

NFD 是在 NF 前先将物品根据其大小按降序排列。

FF/FFD算法

FF(First Fit) 即首次适应算法 , 当放置某个新到来的物品 a 时 , 把它放到已使用的指标最小的箱子里 , 只有当所有的非空箱子都不能放 a 时 , 才打开一个新箱子 。

FFD 是在 FF 前先将物品根据其大小降序排列。

标签:

评论已关闭!