回复 2 楼 embed_xuel
这是整个程序
/* 0/1背包问题的分支定界法算法*/
#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 100
struct node
{
int step ;
double price ;
double weight ;
double max,min ;
unsigned long po ;
};
typedef struct node DataType ;
struct SeqQueue
{
/* 顺序队列类型定义 */
int f,r ;
DataType q[MAXNUM];
}
;
typedef struct SeqQueue*PSeqQueue ;
PSeqQueue createEmptyQueue_seq(void)
{
PSeqQueue paqu ;
paqu=(PSeqQueue)malloc(sizeof(struct SeqQueue));
if(paqu==NULL)
printf("Out of space!! \n");
else
paqu->f=paqu->r=0 ;
return paqu ;
}
int isEmptyQueue_seq(PSeqQueue paqu)
{
return paqu->f==paqu->r ;
}
/* 在队列中插入一元素x */
void enQueue_seq(PSeqQueue paqu,DataType x)
{
if((paqu->r+1)%MAXNUM==paqu->f)
printf("Full queue.\n");
else
{
paqu->q[paqu->r]=x ;
paqu->r=(paqu->r+1)%MAXNUM ;
}
}
/* 删除队列头元素 */
void deQueue_seq(PSeqQueue paqu)
{
if(paqu->f==paqu->r)
printf("Empty Queue.\n");
else
paqu->f=(paqu->f+1)%MAXNUM ;
}
/* 对非空队列,求队列头部元素 */
DataType frontQueue_seq(PSeqQueue paqu)
{
return(paqu->q[paqu->f]);
}
/* 物品按性价比从新排序*/
void sort(int n,double p[],double w[])
{
int i,j ;
for(i=0;i<n-1;i++)
for(j=i;j<n-1;j++)
{
double a=p[j]/w[j];
double b=p[j+1]/w[j+1];
if(a!=b)
{
double temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
temp=w[j];
w[j]=w[j+1];
w[j+1]=temp;
}
}
}
/*求最大可能值*/
double up(int k,double m,int n,double p[],double w[])
{
int i=k;
double s=0;
while(i!=n&&w[i]!=m)
{
m-=w[i];
s+=p[i];
i++;
}
if(i!=n&&m>0)
{
s+=p[i]*m/w[i];
i++;
}
return s;
}
/* 求最小可能值*/
double down(int k,double m,int n,double p[],double w[])
{
int i=k ;
double s=0 ;
while(i<n&&w[i]!=m)
{
m-=w[i];
s+=p[i];
i++;
}
return s ;
}
/* 用队列实现分支定界算法*/
double solve(double m,int n,double p[],double w[],unsigned long*po)
{
double min ;
PSeqQueue q=createEmptyQueue_seq();
DataType x=
{
0,0,0,0,0,0
};
sort(n,p,w);
x.max=up(0,m,n,p,w);
x.min=min=down(0,m,n,p,w);
if(min==0)return-1 ;
enQueue_seq(q,x);
while(!isEmptyQueue_seq(q))
{
int step ;
DataType y ;
x=frontQueue_seq(q);
deQueue_seq(q);
if(x.max<min) continue;
step=x.step+1;
if(step==n+1) continue;
y.max=x.price+up(step,m-x.weight,n,p,w);
if(y.max>=min)
{
y.min=x.price+down(step,m-x.weight,n,p,w);
y.price=x.price ;
y.weight=x.weight ;
y.step=step ;
y.po=x.po<<1;
if(y.min>=min)
{
min=y.min;
if(step==n)*po=y.po;
}
enQueue_seq(q,y);
if(x.weight+w[step-1]<=m)
{
y.max=x.price+p[step-1]+
up(step,m-x.weight-w[step-1],n,p,w);
if(y.max>=min)
{
y.min=x.price+p[step-1]+down(step,m-x.weight-w[step-1],n,p,w);
y.price=x.price+p[step-1];
y.weight=x.weight+w[step-1];
y.step=step;
y.po=(x.po<<1)+1;
if(y.min>=min)
{
min=y.min;
if(step==n)*po=y.po;
}
enQueue_seq(q,y);
}
}
}
return min ;
}
#define n 4
double a=15 ;
double b[n]=
{
10,10,12,18
};
double c[n]=
{
2,4,6,9
};
int main()
{
int i;
double d;
unsigned long po;
d=solve(a,n,b,c,&po);
if(d==-1)
printf("No solution!\n");
else
{
for(i=0;i<n;i++)
printf("x%d is %d\n",i+1,((po&(1!=(n-i-1)))!=0));
printf("The max weight is %f\n",d);
}
getchar();
return 0;
}
