/* * 装箱问题 * 算法：贪婪 * coder:瞿鹏志 * time：2014-11-29 */ #include <stdlib.h> #include <iostream> using namespace std; #define MAX 20 /*
第一步：创建物品字典
*/ typedef struct { int gno;//编号 int ver;//占用空间 }Gnode; Gnode *bh(int n); void prinGnode(Gnode *a,int n); /*
第二步：创建箱子
*/ //1.箱子里所装的物品 typedef struct gnode{ int gno;//编号 struct gnode *gnext;//指向物品 }GGnode; //2.箱子 typedef struct box{ int ver;//箱子体积 GGnode *gnext;//指向箱中物品 struct box *bnext;//指向下一个箱子 }Box; //打开新箱子 Box *OpenBox(void); //创建物品结点 GGnode *GreatLink(int gno); /*
第三步：装箱
贪心算法 */ Gnode *SortGno(Gnode *a,int n);//排序 GGnode *Put(int gno);// 物品放入箱子 Box *PackingBox(Gnode *a,int n);//处理过程 void prinBoxG(Box *p,Gnode *dic);//输出箱子中物品的信息 void prinBox(Box *a,Gnode *dic);//输出箱子信息 int main(void) { Gnode *a,*b; Box *box; int n=0; cout<<"请输入物品个数："; cin>>n; if(n){ a=bh(n); cout<<"排序前"; prinGnode(a,n); b=SortGno(a,n); cout<<"排序后"; prinGnode(b,n); box=PackingBox(b,n); prinBox(box,a); free(a); free(b); }else{ cout<<"没有物品，不用打开箱子"<<endl; } return 0; } //创建物品字典 Gnode *bh(int n) { Gnode *a=(Gnode *)malloc(n*sizeof(Gnode)); for(int i=0;i<n;i++){ a[i].gno=i+1; cout<<"请输入第"<<a[i].gno<<"个物品的体积"; cin>>a[i].ver; } /*end for*/ cout<<"物品数据库创建成功！！！"<<endl; cout<<endl; return a; } //输出物品字典 void prinGnode(Gnode *a,int n) { cout<<"物品表输出:"<<endl; for(int i=0;i<n;i++){ cout<<"编号:"<< a[i].gno<<","<<"体积:"<<a[i].ver<<endl; }/*end for*/ cout<<endl; } //排序 Gnode *SortGno(Gnode *a,int n) { Gnode *b=(Gnode *)malloc(n*sizeof(Gnode)); Gnode t; for(int i = 0;i < n; i++){ b[i]=a[i]; }/*end for*/ for(int i=0;i<n;i++){ int max; for(int j=max=i;j<n;j++){ if(b[j].ver>b[max].ver){ max=j; }/*end if*/ }/*end for2*/ t=b[i]; b[i]=b[max]; b[max]=t; }/*end for1*/ return b; } //打开新箱子 Box *OpenBox(void) { Box *head; head=(Box *)malloc(sizeof(Box)); head->ver=MAX; head->gnext=NULL; head->bnext=NULL; return head; } //放入物品 GGnode *Put(int gno) { GGnode *gp=(GGnode *)malloc(sizeof(GGnode)); gp->gno=gno; gp->gnext=NULL; return gp; } /* //装箱 Box *PackingBox(Gnode *a,int n) { Box *head,*p,*qb; GGnode *gp,*qg; head=p=OpenBox(); for(int i = 0;i < n; i++){ //是否超过箱子最大容量 是 箱子装不下 输出编号 continue if(a[i].ver > MAX){ cout<<"编号为"<<a[i].gno<<"的物品体积过大"<<endl; continue; }/*end if*/ /* qb=p; //判断已开箱子可否存入 while(p&&(a[i].ver > p->ver)){ qb=p; p=p->bnext; } //while //没有已开箱子可以装下物品 if(!p){ //1.开新箱子 qb->bnext=p=OpenBox(); } /*end if*/ //装箱 //1.修改箱子容量 /* p->ver-=a[i].ver; //2.放入物品 for(qg=gp=p->gnext;gp;qg=gp,gp=gp->gnext); if(!qg) p->gnext=Put(a[i].gno); else qg->gnext=Put(a[i].gno); }/*end for 遍历物品*/ /* if(head->ver == MAX){ head=NULL; } return head;//箱子头结点地址; }*/ GGnode *GreatLink(int gno) { GGnode *g=(GGnode *)malloc(sizeof(GGnode)); g->gno=gno; g->gnext=NULL; return g; } //装箱 Box *PackingBox(Gnode *a,int n) { Box *head=NULL,*p,*tb; GGnode *gp,*qg,*newg; for(int i = 0;i < n; i++){ //跑箱子 for(p=head;p&&(p->ver<a[i].ver);p=p->bnext); if(!p){ //是否超过箱子最大容量 是 箱子装不下 输出编号 if(a[i].ver > MAX){ cout<<"编号为"<<a[i].gno<<"的物品体积过大"<<endl; continue; }/*end if*/ //1.开新箱子 p=OpenBox(); if(!head){ head=tb=p; } else{ cout<<1<<p; //挂链 tb->bnext=p; cout<<2; tb=tb->bnext; cout<<3; }/*if(!p)*/ } //装箱 //1.修改箱子剩余容量 p->ver-=a[i].ver; //2.放入物品 newg=GreatLink(a[i].gno); for(qg=p->gnext;qg&&qg->gnext;qg=qg->gnext); if(!qg){ p->gnext=newg; }else{ qg->gnext=newg; } }/*end for 遍历物品*/ return head;//箱子头结点地址; } //输出箱子中物品的信息 void prinBoxG(Box *p,Gnode *dic) { if(p->gnext){ cout<<"箱子中物品有："<<endl; for(GGnode *gp=p->gnext;gp;gp=gp->gnext){ cout<<"物品编号"<<gp->gno<<" 物品体积:"<<dic[gp->gno-1].ver<<endl; }/*end for in*/ }else{ cout<<"箱子中没有物品"<<endl; } } //输出箱子信息 void prinBox(Box *a,Gnode *dic) { int cnt=0; for(Box *p=a;p;p=p->bnext){ cout<<"箱子编号:"<<++cnt<<" 箱子剩余空间为:"<<p->ver<<endl; prinBoxG(p,dic); cout<<endl; }/*end for out*/ cout<<"共打开"<<cnt<<"个箱子"<<endl; }
