算法装箱问题.docx

《算法装箱问题.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析练习1：装箱问题设有编号为0,1...，n-1的n种物品，体积分别为V0，V1，...，Vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，要求使装进这n种物品的箱子书要少。算法分析：设置变量：物品个数，箱子体积，每个物品的体积。将所有物品按降序排列；物品装箱；得到所用箱子个数。#include#include#defineV10//物品信息声明：物品编号与物品体积typedefstruct{intgno;intgv;}GInfor;//物品结点类型声明typedefstructgnode{intgno;stru

2、ctgnode*next;}GNode;//箱子结点类型声明typedefstructbnode{intremainder;GNode*firstg;structbnode*next;}BNode;//对物品信息进行降序排列voidSortD(GInfor*g,intn){inti,j;GInfort;for(i=0;ig[i].gv){t=g[j];g[j]=g[i];g[i]=t;}}}}BNode*PackingBox(GInfor*g,intn){BNode*h=NULL;BNode*p=NULL;BNod

3、e*tail=NULL;GNode*newg=NULL;inti;for(i=0;iremaindernext);if(p==NULL){//需要开新箱子p=(BNode*)malloc(sizeof(BNode));p->remainder=V;p->firstg=NULL;p->next=NULL;if(!h)//因为无头结点需要开新箱子h=tail=p;else{//因为现有的所有箱子剩余容积均不够需开新箱子tail=tail->next=p;}}//向确定要放入物品的箱子（不论新旧）放入物品newg=(GNode*

4、)malloc(sizeof(GNode));newg->gno=g[i].gno;newg->next=p->firstg;p->firstg=newg;printf("thething'svis%d",g[i].gv);p->remainder-=g[i].gv;}returnh;}intmain(void){intGnum,i,Bnum;GInfor*g=NULL;BNode*hBox=NULL;BNode*p=NULL;printf("Pleaseinputthenumberofthings");scanf("%d",&Gnum);//创建动态数组存放所有物品信息g=(GInfor*)

5、malloc(Gnum*sizeof(GInfor));for(i=0;inext,Bnum++);printf("Thenumberofboxis:%d",Bnum);return0;}运行结果如图所示：