knap.cpp

动态规划算法求解0-1背包问题,动态规划算法knapsack求最优值

#include "Knap.h"

void Knap::print()
{
	for(int m=1;m<=n;m++)
	{
		cout<<bestx[m]<<" ";
	}
	cout<<endl;
};


//计算上界
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;
}

void Knap::Backtrack(int i)
{
	if(i>n)
	{
		if(bestp<cp)
		{
			for(int j=1;j<=n;j++)
				bestx[j] = x[j];
			bestp = cp;
		}
		return;
	}

	if(cw+w[i] <= c) //搜索左子树
	{             
		x[i] = 1;
		cw += w[i];
		cp += p[i];
		Backtrack(i+1);
		cw -= w[i];
		cp -= p[i];
	}

	if(Bound(i+1)>bestp)//搜索右子树
	{
		x[i] = 0;
		Backtrack(i+1);
	}
}


//为Knap::Backtrack初始化

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

	Object *Q = new Object[n];

	for(i=1;i<=n;i++)
	{
		Q[i-1].ID = i;
		Q[i-1].d = 1.0 * p[i] / w[i];
		P += p[i];
		W += w[i];
	}

	if(W <= c)
		return P;//装入所有物品

	//依物品单位重量排序
	float f;
	for( i=0;i<n;i++)
		for(int j=i;j<n;j++)
		{
			if(Q[i].d < Q[j].d)
			{
				f = Q[i].d;
				Q[i].d = Q[j].d;
				Q[j].d = f;
			}
		}

		Knap  K;
		K.p = new int[n+1];
		K.w = new int[n+1];
		K.x = new int[n+1];
		K.bestx = new int[n+1];

		K.x[0]=0;
		K.bestx[0]=0;

		for( i = 1;i<= n;i++)
		{
			K.p[i] = p[Q[i-1].ID];
			K.w[i] = w[Q[i-1].ID];
		}

		K.cp=0;
		K.cw=0;
		K.c=c;
		K.n=n;
		K.bestp=0;

		//回溯搜索

		K.Backtrack(1);
		K.print();

		delete [] Q;
		delete [] K.w;
		delete [] K.p;
		return K.bestp;
}