背包问题代码.txt

背包问题c算法实现

#include<iostream.h>   
    
  #define   MAX   10000000000   
  #define   MIN   -1000000000   
    
  typedef   struct   goods{   
  int   Weight;   
  float   Value;   
  float   vpw;   
  }goods; //定义物品数据结构   
    
  typedef   struct   Linknode{   
  float   curmaxval;   
  int   flag;   
  int   curweight;   
  int   *fchoice;   
  int   current;   
  Linknode   *next;   
  }Linknode; //定义链表结点数据结构   
    
  void   Inputgoods(goods   *,int);//输入函数声明   
  void   Sortgoods(goods   *,int);   //排序函数声明   
  int   Boundgoods(goods   *,int,int);       //边界处理函数声明   
  int   *Kolesar(goods   *   ,int,int,float&);     //Kolesar算法求被包问题   
  float   Getmaxvalue(goods   *,int   ,int   ,int);//求最大价值函数声明   
  /////////////////////////////////////////////////////////////////////////////////
/////////                     main()
///////////////////////////////////////////////////////////////////////////////////  
  void   main()   
  {   
  int   WS;   
  cout<<"请输入背包最大所承质量：";   
  cin>>WS;   
  cout<<endl;   
    
          int   N;   
  cout<<"请输入物品的数目：";   
  cin>>N;   
  cout<<endl;   
    
    
    
  goods   *Tgoods=new   goods[N];         //动态分配N个物品的空间   
    
  Inputgoods(Tgoods,N);                     //输入物品的相关量   
          Sortgoods(Tgoods,N);                       //依照单位价值进行排序   
    
          int   flag;   
  flag=Boundgoods(Tgoods,N,WS);     //对边界情况进行处理   
    
          if(flag==-1)   
  {   
  cout<<"背包太小，一件物品也装不上"<<endl;   
  return;   
  }   
  if(flag==0)   
  {   
  cout<<"背包可以装下所有物品"<<endl;   
  return;   
  }   
    
  int   *choice=new   int[N];             //选择数组   
  float   Maxvalue;   
  choice=Kolesar(Tgoods,N,WS,Maxvalue);   
  cout<<"背包所装最大价值是："<<Maxvalue<<endl;   
  cout<<"所选物品是："<<endl;   
  for(int   i=0;i<N;i++)   
  {   
  if(choice[i])   
  cout<<i<<"物品"<<"     "<<endl;   
  }   
    
  }   //main()
    
   //////////////////////////////////////////////////////////inputgoods 
  void   Inputgoods(goods   *Fgoods,int   N)   
  {   
  cout<<"请输入物品的重量和价值"<<endl;   
  for(int i=0;i<N;i++)   
  {   
  cout<<"W["<<i<<"]=";   
  cin>>Fgoods[i].Weight;   
  cout<<"V["<<i<<"]=";   
  cin>>Fgoods[i].Value;   
  cout<<endl;   
  Fgoods[i].vpw=Fgoods[i].Value/(float)Fgoods[i].Weight;   
          }   
  }   
   /////////////////////////////////////////////////////////////////////sort 
  void   Sortgoods(goods   *Fgoods,int   N)                       //利用选择法通过权值大小对所有物品排序   
  {   
  goods   tempgoods;   
  float   max;   
  int  	  k;   
  for(int i=0;i<N;i++)   
  {   
  max=Fgoods[i].vpw;  //Fgoods[i].vpw=Fgoods[i].Value/(float)Fgoods[i].Weight  
  k=i;   
  for(int j=i+1;j<N;j++)   
  {   
  if(max<Fgoods[j].vpw)   
  {   
  k=j;   
  max=Fgoods[j].vpw;   
  }   //if
  }   
  if(k!=i)   ///////////////////////////////////////////////交换temp=b;b=a;a=temp;可以定义指针优化????????????????????????????????????
  {   
  tempgoods.Value=Fgoods[i].Value;   
  tempgoods.vpw=Fgoods[i].vpw;   
  tempgoods.Weight=Fgoods[i].Weight;   
    
  Fgoods[i].Value=Fgoods[k].Value;   
  Fgoods[i].vpw=Fgoods[k].vpw;   
  Fgoods[i].Weight=Fgoods[k].Weight;   
    
  Fgoods[k].Value=tempgoods.Value;   
  Fgoods[k].vpw=tempgoods.vpw;   
  Fgoods[k].Weight=tempgoods.Weight;   
  } //for(int j=i+1;j<N;j++)  
  }//for(int i=0;i<N;i++)   
  }   
    
    
  ////////////////////////////////////////////////////////////边界处理  
  int   Boundgoods(goods   *Fgoods,int   N,int   Weight)   //weight:背包最大所承质量
  {   
  int   flag=0;   
  int   totalweight=0;   
  for(int i=0;i<N;i++)   
  {   
  totalweight+=Fgoods[i].Weight;   
  if(Fgoods[i].Weight<Weight)//??????????????????????????????????????????????????如果有一个Fgoods[i].Weight>Weight，则可能报错   
  flag=1;   
  }   
  if(totalweight<Weight)   
  return   0;   
  if(!flag)   
  return   -1; //flag 0  即Fgoods[i].Weight>Weight?????????????????????????????????????????????????????????????
  return   1;   
  }   
 //////////////////////////////////////////////////////////////  边界处理       优化
  /*int   Boundgoods(goods   *Fgoods,int   N,int   Weight)   //weight:背包最大所承质量
  {   
  int   flag=0;   
  int   totalweight=0;   
  for(int i=0;i<N;i++)   
  {   
  totalweight+=Fgoods[i].Weight;   
  if(Fgoods[i].Weight<Weight)   
  flag=1;   
  }   
  if(totalweight<Weight)   
  return   0;   
  if(!flag)   
  return   -1; //flag 0  即Fgoods[i].Weight>Weight
  return   1;   
  } 
*/ 
 /////////////////////////////////////////////////////////////////////////求最大值
  float   Getmaxvalue(goods   *Fgoods,int   N,int   start,int   curweight)   
  {   
  float   maxvalue=0;   
    
  for(int   i=start;i<N&&curweight>Fgoods[i].Weight;i++)   
  {   
  maxvalue+=Fgoods[i].Value;   
  curweight-=Fgoods[i].Weight;   
  }   
  if(i!=N)   
  maxvalue+=Fgoods[i].vpw*curweight;   
  return   maxvalue;   
  }   
 /////////////////////////////////////////////////////////////////////////kolesar算法  
  int   *Kolesar(goods   *Fgoods,int   N,int   weight,float&   Maxvalue)   
  {   
  Linknode   *search,*build,*head,*tag,*tail;   
  float   maxval;   
    
  search=build=head=tag=tail=new   Linknode;   
  head->curmaxval=Getmaxvalue(Fgoods,N,0,weight);   
  head->flag=0;   
  head->curweight=weight;   
  head->fchoice=new   int[N];   
  for(int i=0;i<N;i++)   
  head->fchoice[i]=0;   
  head->current=0;   
  head->next=NULL;   
  for(;;)   
  {   
  tag=search=head;   
                  maxval=MIN;   
  while(search!=NULL)                               //找出当前价值上界最大的可扩展节点tag   
  {   
  if(!search->flag&&search->curmaxval>maxval)   
  {   
  maxval=search->curmaxval;   
  tag=search;   
  }   
  search=search->next;   
  }   
    
  if(tag->current==N)   
  {   
  Maxvalue=tag->curmaxval;   
  return   tag->fchoice;   
  }   
    
  tag->flag=1;   
    
  build=new   Linknode;                       //生成选择当前物品的结点   
  build->fchoice=new   int[N];   
  build->next=NULL;   
  tail->next=build;   
  tail=build;   
  if(tag->curweight<Fgoods[tag->current].Weight)   
  {   
  build->curmaxval=MIN;   
  build->flag=1;   
  }   
  else   
  {   
  build->curmaxval=tag->curmaxval;   
  build->flag=0;   
  build->curweight=tag->curweight-Fgoods[tag->current].Weight;   
  build->current=tag->current+1;   
  for(int   i=0;i<tag->current;i++)   
  {   
  build->fchoice[i]=tag->fchoice[i];   
  }   
  build->fchoice[tag->current]=1;   
  } 
    
  build=new   Linknode;                   //生成不选择当前物品的节点   
  build->fchoice=new   int[N];   
  build->next=NULL;   
  tail->next   =build;   
  tail=build;   
  int     curweight=0;   
  float   curvalue=0;   
  for(int   i=0;i<tag->current;i++)   
  {   
  curweight+=tag->fchoice[i]*Fgoods[i].Weight;   
  curvalue+=tag->fchoice[i]*Fgoods[i].Value;   
  }   
    
  if(tag->curweight<Fgoods[tag->current].Weight)   
  {   
  build->curmaxval=curvalue+Getmaxvalue(Fgoods,N,tag->current+1,tag->curweight);   
  }   
  else   
  {   
  build->curmaxval=curvalue+Getmaxvalue(Fgoods,N,tag->current+1,tag->curweight);   
  }   
  build->flag=0;   
  build->curweight=tag->curweight;   
  build->current=tag->current+1;   
    
                          for(   i=0;i<tag->current;i++)   
  {   
  build->fchoice[i]=tag->fchoice[i];   
  }   
  build->fchoice[tag->current]=0;   
  }  ////for(;;) 
    
  }   ////*Kolesar