本文实例讲述了C语言基于贪心算法解决装箱问题的方法。贪心算法中要求每一步的解都是当前步骤中的最优解。原问题的解可以通过一系列局部最优的选择来达到,这种选择并不依赖于子问题的解。要求求解箱子数目,也就是说不能确定会占用多少个箱子,因此采用链表的形式来存储箱子及其信息。由此得出数据节点的定义:使打开的箱子数尽量少,也就是说每个箱子容积被尽可能多地占用。将物品按照体积降序排列后,再从第一个物品开始,挨个寻找能放下它的箱子,这样可以保证局部最优。排序完成,就可以正式开始装箱子了。如果所有的已经打开的箱子都放不下当前的物品,那就只好再打开一个空箱子,把它塞进去。希望本文所述对大家C语言程序设计有所帮助。
暂无评论