C语言基于贪心算法解决装箱问题的方法
本文实例讲述了C语言基于贪心算法解决装箱问题的方法。分享给大家供大家参考,具体如下:
问题描述:
有一些箱子,容量为V,同时有n个物品,每个物品有一个体积(小于等于箱子容量),要求将物品全部装入箱子中,使占用的箱子数尽量少。
贪心算法中要求每一步的解都是当前步骤中的最优解。原问题的解可以通过一系列局部最优的选择来达到,这种选择并不依赖于子问题的解。
算法思想:
1、数据结构
要求求解箱子数目,也就是说不能确定会占用多少个箱子,因此采用链表的形式来存储箱子及其信息。
同时,每个箱子中物品的数目也无法确定,同理采用链表来存储每个箱子中的物品信息。
由此得出数据节点的定义:
typedefstruct { intgno; intgv; }Goods; typedefstructnode { intgno; structnode*link; }GNode; typedefstructnode1 { intremainder; GNode*head; structnode1*next; }GBox;
2、求解思路
使打开的箱子数尽量少,也就是说每个箱子容积被尽可能多地占用。将物品按照体积降序排列后,再从第一个物品开始,挨个寻找能放下它的箱子,这样可以保证局部最优。
voidGoodsSort(Goodsgoods[],intn) { inti,j; Goodst; for(i=0;i排序完成,就可以正式开始装箱子了。
每次都从第一个箱子开始,查看它的剩余容积还能不能放下当前的物品,能放下最好咯,放不下的话就继续查看下一个箱子的剩余容量。如果所有的已经打开的箱子都放不下当前的物品,那就只好再打开一个空箱子,把它塞进去。
GBox*GoodsBox(Goodsgoods[],intn) { GNode*h=NULL,*pg,*t; GBox*hbox=NULL,*pb,*qb; inti; for(i=0;igno=goods[i].gno; pg->link=NULL;//货物节点初始化 if(!hbox)//若一个箱子都没有 { hbox=(GBox*)malloc(sizeof(GBox)); hbox->remainder=10; hbox->head=NULL; hbox->next=NULL; } qb=pb=hbox;//都指向箱子头 while(pb)//找箱子 { if(pb->remainder>=goods[i].gv)/////////////////////////////能装下 break;//找到箱子,跳出while else { qb=pb; pb=pb->next;//qb是前驱 } }/////////////////////////////////////遍历箱子结束 if(pb==NULL)/////////////////////需要新箱子 { pb=(GBox*)malloc(sizeof(GBox));//分配箱子 pb->head=NULL; pb->next=NULL; pb->remainder=10;//初始体积 qb->next=pb;//前驱指上 } if(!pb->head)//如果箱子里没货 { pb->head=pg; t=pb->head; } else { t=pb->head; while(t->link)t=t->link;//货尾尾插 t->link=pg; } pb->remainder-=goods[i].gv; ////////////////////////////////////装箱 } returnhbox; 希望本文所述对大家C语言程序设计有所帮助。