Chinaunix首页 | 论坛 | 博客
  • 博客访问: 123003
  • 博文数量: 32
  • 博客积分: 1410
  • 博客等级: 上尉
  • 技术积分: 340
  • 用 户 组: 普通用户
  • 注册时间: 2005-06-04 21:53
文章分类

全部博文(32)

文章存档

2008年(9)

2007年(6)

2006年(8)

2005年(9)

我的朋友

分类: C/C++

2006-05-01 17:20:49

0/1背包问题:
偶是使用序偶数列来写程序的, 结果正确.运行正常
只是觉得算法过于复杂, 程序有些罗嗦. 高手帮忙修改一下!万分感谢!
程序如下:
#include
typedef struct Node
{
 int value;
 int weight;
 Node *next;
}Node;
int input();                            //输入有效值
void prints(Node *n);                   //输出Si的值
void count(Node **s,int number,Node *p);//计算Si的值
void detect(Node **s,int n);            //删除逆序序偶
void free(Node **s, Node *p);           //释放空间
void whichx(Node **s,Node *p,int weight_all,int x[],int number);//计算X有无被选取
void main()
{
 int number,weight_all;
    Node *p=new Node;
 Node *p_first=p;
 int x[20];
   
 cout<<"Input the number of the goods:   ";
    number=input();
 cout< weight_all=input();
 for(int i=0;i {
  cout<  p->value=input();
  cout<  p->weight=input();
  p->next=new Node;
  p=p->next;
 } 
  cout<  p->value=input();
  cout<  p->weight=input();
     p->next=NULL;   //完成输入
 //////////////////////////// 
 p=p_first;
 cout<<"===========P==========="< prints(p);
 p=p_first;
 Node *s[21];
 for(int k=0;k<=20;k++)
 {
  s[k]=new Node;
  s[k]->next=NULL;
 }
 s[0]->value=0;
    s[0]->weight=0;
 s[0]->next=NULL;//初使化S(0)
  count(s,number,p);//计算S(i)
    detect(s,number);  //删除逆序序偶
 for(int l=0;l<=number;l++)
 {
  cout<  prints(s[l]);  
 }
 cout<
 ///////计算所取的物品/////////
 whichx(s,p,weight_all,x,number);
 ////////////
 for(int m=1;m<=number;m++)
  cout<
 cout< free(s,p);  //释放空间
}
///////////////////////////////////////////////////////////////////////
int input()
{
 int number;
 cin>>number;
 while(number<=0)
 {
  cout<<"The number is ill";
  cin>>number;
 }
 return number;
}
void prints(Node *n)
{
 while(n!=NULL)
 {
  cout<<"{"<value<<" , "<weight<<"}"<<"   ";
  n=n->next;
 }
}
void count(Node **s,int number,Node *p)
{//计算Si
 Node *s_first;
 Node *front_first;
 for(int j=1;j<=number;j++)
 {
  s_first=s[j];
  front_first=s[j-1];
        //循环拷贝前面的数值
  while(front_first!=NULL)
  {           
   s_first->value=front_first->value;
      s_first->weight=front_first->weight;   //将前面的拷贝过去 
   s_first->next=new Node;
   s_first=s_first->next;
   s_first->next=NULL;   
   front_first=front_first->next;
  }
  front_first=s[j-1];
  //加上Pi后在值
  while(front_first!=NULL)
  {
   s_first->value=front_first->value+(p->value);
   s_first->weight=front_first->weight+(p->weight); //加上PI,WI
   if(front_first->next!=NULL)
   {
    s_first->next=new Node;
    s_first=s_first->next;
    s_first->next=NULL;
   }
   front_first=front_first->next;
  }
  p=p->next;
 }//for(计算Si)
}
void detect(Node **s,int number)
{//删除序列中逆序的序偶
 for(int j=0;j<=number;j++)
 {
  Node *s_s=s[j]->next;
  Node *s_first=s[j];
  for(s_s;s_s!=NULL;s_s=s_s->next)
  {
   Node *s_follow=s_s->next;
   for(s_follow;s_follow!=NULL;s_follow=s_follow->next)
   {
    if((s_s->value)<(s_follow->value)
     &&(s_s->weight)>(s_follow->weight))
    {
     s[j]->next=s_s->next;
     s_s=s[j]->next;
     s_follow=s_follow->next;
    }
   }
   s[j]=s[j]->next;
  }
  s[j]=s_first;
 }
}
void whichx(Node **s,Node *p,int weight_all,int x[],int number)
{
 int max_value;
 int max_weight;
 for(int i=number;i>0;i--)
 {
  Node *n=s[i];
  max_value=n->value;
  max_weight=n->weight;
  n=n->next;
  while(n!=NULL)
  {
   if((n->weight<=weight_all)&&(n->value>max_value))
   {
    max_value=n->value;
    max_weight=n->weight;
   }
   n=n->next;
  }
  n=s[i-1];
  while(n!=NULL)
  {
   if((n->weight==max_weight)&&(n->value==max_value))
   {//如果在S[i-1]中也有该序偶,则该物品不放入背包
    x[i]=0;
    break;
   }
   n=n->next;
  }
  if(n==NULL)
  {
   x[i]=1;//放该物品进背包
   n=p;
   for(int j=1;j    n=n->next;
   weight_all-=n->weight;
  }
 }
}
void free(Node **s,Node *p)
{//释放空间
    if(p->next==NULL&&p!=NULL) delete p;
    else
 {
  Node *n=p->next;
  while(n!=NULL)
  {
   delete p;
   p=n;
   n=n->next;   
  }
  delete p;
 }
    for(int i=0;i<=10;i++)
 {
  if((s[i]->next)==NULL&&s[i]!=NULL) delete s[i];
  else
  {
   Node *n=s[i]->next;
   while(n!=NULL)
   {
    delete s[i];
    s[i]=n;
    n=n->next;   
   }
   delete s[i];
  }
 }
}
阅读(1595) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~