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];
}
}
}
阅读(1654) | 评论(1) | 转发(0) |
