背包问题(改进).cpp

经典算法之背包问题

#include <stdio.h>

int Knapsack(int n,int c,int v[],int w[],int **p,int x[])
{
	void Traceback(int n,int w[],int v[],int **p,int *head,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;
			int 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];
			}
			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;
			}
			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];
		}
		left=right+1;
		right=next-1;
		head[i-1]=next;
	}
	Traceback(n,w,v,p,head,x);
//	printf("%d\n",next-1);
	return p[next-1][1];
	
}

void Traceback(int n,int w[],int v[],int **p,int *head,int x[])
{
	int 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;
			}
		}
	}
	return;
}

int main()
{
	int max,
		n,//=5,
		c;//=10,
		//w[6]={0,2,2,6,5,4},	//第一个数字无效
		//v[6]={0,6,3,5,4,6};	//第一个数字无效
	//int x[6];	//结果
	printf("n=");
	scanf("%d",&n);
	printf("c=");
	scanf("%d",&c);
	int *w=new int [n+1],
		*v=new int [n+1],
		*x=new int [n+1];
	printf("w[]=");
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	int sum=0;
	printf("v[]=");
	for(i=1;i<=n;i++)
	{
		scanf("%d",&v[i]);
		sum+=v[i];
	}
	int a[100][2];
	int *q[100];
	for(i=0;i<100;i++)
		q[i]=a[i];
	int **p=q;
	max=Knapsack(n,c,v,w,p,x);
	printf("\n最大价值为:%5d\n",max);
	printf("选择物品的序列为:");
	for(i=1;i<6;i++)
		printf("%5d",x[i]);
	printf("\n");
	return 0;
}