fenzhidingjie beibao .txt

分支定界的0/1背包问题

/* 0/1背包问题的分支定界法算法*/


#include<stdio.h>
#include<stdlib.h>
#define n 4

double m=15;
double p[n]={10,10,12,18};
double w[n]={2,4,6,9};


/* 物品按性价比从新排序*/
void sort(void){
	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;
				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 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 i=k;
	double s=0;
	while(i<n&&w[i]<=m)	//p;w
	{
		m-=w[i];
		s+=p[i];
		i++;
	}
	return s;
}

#define  MAXNUM   100
struct node{
	int step;
	double price;
	double weight;
	double max,min;
	unsigned long po;
};

typedef struct node DataType;
struct  SeqQueue		/* 顺序队列类型定义 */
{
  DataType  q[MAXNUM];
  int  f,r;
};
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 = 0;
		 paqu->r = 0;
	}
	return (paqu);
}

int  isEmptyQueue_seq( PSeqQueue paqu )
{
      return (paqu->f == paqu->r);
}

void  enQueue_seq( PSeqQueue paqu, DataType x )
/* 在队列中插入一元素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]);
}


/* 用队列实现分支定界算法*/
double solve(unsigned long* po){
	double min;
	PSeqQueue q=createEmptyQueue_seq();
	DataType x={0,0,0,0,0,0};
	sort();
	x.max=up(0,m);
	x.min=min=down(0,m);
	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);
		if(y.max>=min){
			y.min=x.price+down(step,m-x.weight);
			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]);
			if(y.max>=min){
				y.min=x.price+p[step-1]+down(step,m-x.weight-w[step-1]);
				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;
}

int main(){
	int i;
	double d;
	unsigned long po;
	d=solve(&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);
	}
	return 0;
}