回溯算法解0--1背包问题.txt

这是一个用回溯算法解0--1背包问题的C++程序（好用的）

#include<iostream.h>//可以用
typedef struct
{float w;
float p;
float v;
}OBJECT;
void merge(OBJECT ob[],int p,int q,int r,int m)
{int *bp=new int[m];
int i,j,k;
i=p;j=q+1;k=0;
while(i<=q&&j<=r){
	if(ob[i].v>=ob[j].v)
		bp[k++]=ob[i++].v;
	else
		bp[k++]=ob[j++].v;
}
if(i==q+1)
{for(;j<=r;j++)
bp[k++]=ob[j++].v;
}
else
{for(;i<=q;i++)
bp[k++]=ob[i++].v;}
k=0;
for(i=p;i<=r;i++)
ob[i++].v=bp[k++];
delete bp;

}
void merge_sort(OBJECT ob[],int n)
{int i,s,t=1;
while(t<n){
	s=t;t=2*s;i=0;
	while(i+t<n){
merge(ob,i,i+s-1,i+t-1,t);
i=i+t;
}
if(i+s<n)
merge(ob,i,i+s-1,n-1,n-i);
}
}

float zhou(OBJECT ob[],float M,int n,int x[])
{int i,k;
float w_cur,p_total,p_cur,w_est,p_est;
int *y=new int[n];
for(i=0;i<=n;i++)
{ob[i].v=ob[i].p/ob[i].w;
y[i]=0;}

merge_sort(ob,n);
w_cur=p_cur=p_total=0;
k=0;
while(k>=0){
	w_est=w_cur;p_est=p_cur;
	for(i=k;i<n;i++){
	w_est=w_est+ob[i].w;
	if(w_est<M)
		p_est=p_est+ob[i].p;
	else
	{p_est=p_est+((M-w_est+ob[i].w)/ob[i].w)*ob[i].p;
	break;
	}
}
if(p_est>p_total){
	for(i=k;i<n;i++)
	{
		if(w_cur+ob[i].w<=M){
			w_cur=w_cur+ob[i].w;
			p_cur=p_cur+ob[i].p;
			y[i]=1;
		}
		else
		{y[i]=0;
		break;
	}
}
	if(i>=n){
if(p_cur>p_total){
	p_total=p_cur;k=n;
	for(i=0;i<n;i++)
		x[i]=y[i];
}
}
else
k=i+1;
}
else
{
	while((i>=0)&&(!y[i]))
i=i-1;
	if(i<0)
		break;
	else{
		w_cur=w_cur-ob[i].w;
		p_cur=p_cur-ob[i].p;
		y[i]=0;
		k=i+1;
	}
}
}
delete y;
return p_total;

	}
void main()
{int n=5;//////物体个数为n
OBJECT ob[5];//存放物体的价值和重量的结构体数组ob[]
float M;//背包的载重量
int x[5];//
int y[5];//
float p_est;
float p_total;
float w_cur;
float p_cur;
M=50.0;
ob[0].w=5;ob[1].w=15;ob[2].w=25;ob[3].w=27;ob[4].w=30;//例子,重量
ob[0].p=12;ob[1].p=30;ob[2].p=44;ob[3].p=46;ob[4].p=50;//价值（权重）
n=5;
float o;
o=zhou(ob,M,n,x);
cout<<"最大0--1背包价值为："<<endl;
cout<<o<<endl;
cout<<"最优解为："<<endl;
for(int i=0;i<n;i++)
cout<<x[i]<<endl;//0--1背包问题的最优解x[]
}