/*
装箱问题 
算法：贪婪 
瞿鹏志 
：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);
/*
 第二步：创建箱子 
 */
箱子里所装的物品 
typedef struct gnode{
 int gno;//编号
指向物品 
}GGnode; 
//2.箱子
typedef struct box{
 int ver;//箱子体积 
 GGnode *gnext;//指向箱中物品 
 struct box *bnext;//指向下一个箱子 
}Box; 
//打开新箱子 
Box *OpenBox(void);
//创建物品结点 
GGnode *GreatLink(int gno);
 /*
  第三步：装箱  
  贪心算法 
 */ 
排序 
物品放入箱子 
处理过程 
输出箱子中物品的信息 
输出箱子信息 
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){
            开新箱子
               qb->bnext=p=OpenBox();
           } /*end if*/
            装箱   
            修改箱子容量 
  /*    p->ver-=a[i].ver;
  放入物品
             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*/
      开新箱子
          p=OpenBox();
 
        if(!head){
           head=tb=p;
        }
         else{
      cout<<1<<p;
    挂链 
   tb->bnext=p; 
        cout<<2;
        tb=tb->bnext;
         cout<<3;       
    }/*if(!p)*/
        }          
            装箱   
            修改箱子剩余容量
              p->ver-=a[i].ver;
  放入物品
        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; 
  
 }