背包问题.cpp

用动态规划的向后处理法求解背包问题的最优决策序列。即给定一个背包序列的重量和相对应的效益值。做出一个最优决策序列Xi(i=1~n)

#include<stdio.h>
bool Done;
int next;
void parts(int P[],int W[],int F[],int x[],int p[],int w[],int n);
int DKNAP(int P[],int W[],int n,int M,int p[],int w[],int x[]);

int DKNAP(int P[],int W[],int n,int M,int p[],int w[],int x[])
{
	int F[128];
	int pp,ww,l,h,u ,i,j,k,r;
	F[0]=1;
	P[1]=W[1]=0;                            //S0//
	l=h=1;                                  //S0的首端与末端//
	F[1]=next=2;                            //P和W中第一个空位//
	for(i=1;i<=n;i++)
	{
		k=r=l;
		Done=false;
		while(r<=h&&!Done)
		{
			if(W[r]+w[i]<=M)                //u为1<=r<=h中使得W[r]+w[i]<=M的最大的r//
			{
				u=r;
				r++;
			}
			else Done=true;
		}
		for(j=l;j<=u;j++)                   //生成S1i及归并//
		{
			pp=P[j]+p[i];
			ww=W[j]+w[i];                   //S1i中的下一个元素//
			while(k<=h&&W[k]<ww)            //从S(i-1)中取元素来归并,S(i-1)中W[k]比ww小的可以直接加入Si//
			{
				P[next]=P[k];
				W[next]=W[k];
				next++;
				k++;
			}
			if(k<=h&&W[k]==ww)              //相等则较大效益值赋值给pp//
			{
				pp=(pp>=P[k])?pp:P[k];
				k++;
			}
			if(pp>P[next-1])                
			{
				P[next]=pp;
				W[next]=ww;
				next++;
			}
			while(k<=h&&P[k]<=P[next-1]) k++;//清除//
		}                                                                                        
		while(k<=h)                          //将S(i-1)中剩余元素并入Si//
		{
			P[next]=P[k];                                      
			W[next]=W[k];                                                                                                                      
			next++;
			k++;
		}
		l=h+1;
		h=next-1;
		F[i+1]=next;
	}
	parts(P,W,F,x,p,w,n);
	return next;
}

void parts(int P[],int W[],int F[],int x[],int p[],int w[],int n)
{
	int a=next-1;
	int b,t,ppt,wwt;
	ppt=P[a];                              //将最末序偶(P,W)赋值给(ppt,wwt)将其初始化用于后来比较//
	wwt=W[a];
	for(b=n;b>=1;b--)                      //用回溯法求出背包问题的最优决策序列x[n]//
	{
		t=F[b-1];                          //t初值// 
		Done=false;                        //布尔变量Done用于控制内层循环
		while(t<F[b]&&!Done)
		{
			if(P[t]==ppt&&W[t]==wwt)       //在S(b-1)中找到(ppt,wwt)则取x(b)=0 
			{                              //否则置x(b)=1,并修改(ppt,wwt)
				x[b]=0;
				Done=true;
			}
			else t++;
		}
		if(t==F[b]) 
		{
			x[b]=1;
			ppt=ppt-p[b];
			wwt=wwt-w[b];
		}
	}
}

void main()
{
	int n,M,c,next=2;
	int P[256],W[256];
	int x[64],p[64],w[64];
	printf("*************算法4.7 0/1背包问题的算法实现*************\n"); 
	printf("请输入物体的个数(1<=n<=64):");
	scanf("%d",&n);
	while(n<1||n>64)
	{
		printf("输入有误!!请重新输入物体个数(1<=n<=64):");
		scanf("%d",&n);
	}
	printf("请输入背包的容量M:");
	scanf("%d",&M);
	while(M<=0)
	{
		printf("输入有误!!请输入一个正整数:");
		scanf("%d",&M);
	}
	printf("以下依次输入物体的效益值和重量:)\n"); 
	for(c=1;c<=n;c++)
	{
		printf("p%d:",c);
		scanf("%d",&p[c]);
		printf("w%d:",c);
		scanf("%d",&w[c]);
		while(w[c]<0)
		{
			printf("输入有误!!请重新输入一个正整数:");
			scanf("%d",&w[c]);
		}
		printf("\n");
	}
		next=DKNAP(P,W,n,M,p,w,x);
		printf("背包问题的最优解为:%d\n",P[next-1]);
		printf("相应的最优决策序列为:");
		for(c=1;c<=n;c++)
			printf("%-4d",x[c]);
}