bag.cpp

算法分析课程中的经典算法

#include<iostream>

using namespace std;
typedef float T;
//template<class T>
void Traceback(int n,T w[],T v[],T p[][2],int *head,int x[])
{
	T j=p[head[0]-1][0],
	m=p[head[0]-1][1];
	for(int i=1;i<=n;i++)
	{
		x[i]=0;
		for(int k=head[i+1];k<=head[i]-1;k++)
		{
			if(p[k][0]+w[i]==j && p[k][1]+v[i]==m)
			{
				x[i]=1;
				j=p[k][0];
				m=p[k][1];
				break;
			}
		}
	}
}
//template<class T>
T Knapsack(int n,int c,T v[],T w[],T p[][2],int x[])
{
	int *head=new int[n+2];
	head[n+1]=0;
	p[0][0]=0;
	p[0][1]=0;
	int left=0,right=0,next=1;
	head[n]=1;

	for(int i=n;i>=1;i--)
	{
		int k=left;
		for(int j=left;j<=right;j++)
		{
			if(p[j][0]+w[i]>c) break;
			T y=p[j][0]+w[i],
			m=p[j][1]+v[i];
			while(k<=right && p[k][0]<y)
			{
				p[next][0]=p[k][0];
				p[next][1]=p[k][1];
				next++;
				k++;
			}
			if(k<=right && p[k][0]==y)
			{
				if(m<p[k][1]) m=p[k][1];
				k++;
			}
			if(m>p[next-1][1])
			{
				p[next][0]=y;
				p[next][1]=m;
				next++;
			}
			while(k<=right && p[k][1]<=p[next-1][1])
			{
				k++;
			}
		}
		while(k<=right)
		{
			p[next][0]=p[k][0];
			p[next][1]=p[k][1];
			next++;k++;
		}
		left=right+1;
		right=next-1;
		head[i-1]=next;
//cout<<next<<" ";
	} 
	Traceback(n,w,v,p,head,x);
	return p[next-1][1];
}

int main()
{
	int i,n,c;
	T maxV;
	T *v;
	T *w;
	int *x;
	T p[65536][2];
	cout<<"\n*********0-1 背包问题动态规划法************"<<endl;
	cout<<"请输入背包个数："<<endl;
	cin>>n;
	cout<<"请输入背包容量："<<endl;
    cin>>c;
	v=new T[n+1];
	w=new T[n+1];
	x=new int[n+1];

	cout<<"请输入个背包的价值："<<endl;
	for(i=1;i<=n;i++) cin>>v[i];
	cout<<"请输入个背包的重量："<<endl;
	for(i=1;i<=n;i++) cin>>w[i];
	cout<<"\n***************运行结果******************\n"<<endl;
    maxV=Knapsack(n,c,v,w,p,x);
	cout<<"Max value is : "<<maxV<<endl;
	for(i=1;i<=n;i++) cout<<x[i]<<" ";
	cout<<endl;
	cout<<"\n*****************************************\n\t\t\t by Vaaa 06-05-31"<<endl;
	delete[] v;
	delete[] w;
	delete[] x;
	return 0;
}