0-1背包的回溯法.cpp

经典算法之背包问题

#include <iostream.h>
#include <stdio.h>
#define MAX 100

class Knap
{
	friend int Knapsack(int *,int *,int,int );
private:
	int Bound(int i);
	void Backtrack(int i);
	int c;
	int n;
	int *w;
	int *p;
	int cw;
	int cp;
	int bestp;
};

int Knap::Bound(int i)
{
	int cleft=c-cw;
	int b=cp;

	while(i<=n&&w[i]<=cleft)
	{
		cleft-=w[i];
		b+=p[i];
		i++;
	}

	if(i<=n)
		b+=p[i]/w[i]*cleft;
	return b;
}
int m;
int kw[MAX];
int kp[MAX];

void Knap::Backtrack(int i)
{
	if(i>n)
	{
		bestp=cp;
		return;
	}
	if(cw+w[i]<=c)
	{
		cw+=w[i];
		cp+=p[i];
		Backtrack(i+1);
		cw-=w[i];
		cp-=p[i];
		kw[m]=w[i];
		kp[m]=p[i];
		m++;
	}
	if(Bound(i+1)>bestp)
		Backtrack(i+1);
}

class Object
{
	friend int Knapsack(int *,int *,int ,int);

public:
	int operator<=(Object a) const
	{
		return (d>=a.d);
	}
	friend void Sort(Object * & Q,int n);
private:
	int ID;
	float d;
};

void Sort(Object* & Q,int n)
{
	Object t;
	for(int j=1;j<=n;j++)
		for(int i=1;i<=3-j;i++)
			if(Q[i+1]<=Q[i])
			{
				t=Q[i];
				Q[i]=Q[i+1];
				Q[i+1]=t;
			}
}


int Knapsack(int p[],int w[],int c,int n)
{
	int P=0;
	int W=0;

	Object *Q= new Object [n];
	for(int i=1;i<=n;i++)
	{
		Q[i-1].ID=i;
		Q[i-1].d=float(1.0*p[i]/w[i]);
		P+=p[i];
		W+=w[i];
	}
	if(W<=c)
		return P;
	Sort(Q,n);
	Knap K;
	K.p=new int [n+1];
	K.w=new int [n+1];
	for(int j=1;j<=n;j++)
	{
		K.p[j]=p[Q[j-1].ID];
		K.w[j]=w[Q[j-1].ID];
	}
	K.cp=0;
	K.cw=0;
	K.c=c;
	K.n=n;
	K.bestp=0;
	K.Backtrack(1);
	delete [] Q;
	delete [] K.w;
	delete [] K.p;
	return K.bestp;
}

void main()
{
    int p[MAX],w[MAX],n,c,next;

	m=0;
	
	printf("背包的最大容量：");
	scanf("%d",&c);
	printf("物品的总数：");
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		printf("%d 物品的重量",i);
		scanf("%d",&w[i]);
		printf("%d 物品的价值",i);
		scanf("%d",&p[i]);
	}
	next=Knapsack(p,w,c,n);

	printf("最优值:");
	printf("%d",next);

	printf("\n最优解(装载物品编号): ");
	for(int j=1;j<=n;j++)
		for(int k=0;k<m;k++)
		{
			if((p[j]==kp[k])&&(w[j]==kw[k]))
			{
				printf("物品%d ",j);
			}
		}

}