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语言程序设计有所帮助。