回溯法解01背包问题.cpp

算法分析中

#include<iostream>
#include<algorithm>
using namespace std;
/*
0-1背包问题也是一个子集选取问题。
为了便于计算上界函数，可先将物品依其单位重量价值从大到小排序
此后只要按顺序考察各物品即可。在实现时，由函数Bound来计算在当前结点处的上界
它是类Knap的私有成员。Knap的其它成员记录解空间树中的结点信息，以减少函数参数的
传递以及递归调用时所需的栈空间。
在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数Bound，以判断
是否可以将右子树剪去。
在调用函数Knapsack之前，需要先将各物品依其单位重量价值从大到小排序。为此目的，
我们定义了类Object。其中,<=运算符与通常的定义相反，其目的是为了方便调用已有
的排序算法。在通常情况下，排序算法将待排序元素从小到大排列。

*/
template<class Typew,class Typep>
class Knap
{
	friend Typep Knapsack(Typep*,Typew*,Typew,int);
	private:
		Typep Bound(int i);
		void Backtrack(int i);
		Typew c;
		//背包的容量
		int n;
		//物品数
		Typew* w;
		//物品重量数组
		Typep* p;
		//物品价值数组
		Typew cw;
		//当前重量
		Typep cp;
		//当前价值
		Typep bestp;
		//当前最优价值
};

template<class Typew,class Typep>
Typep Knap<Typew,Typep>::Bound(int i)
{
	// 计算上界
	Typew eleft = c - cw;
	// 剩余容量
	Typep b = cp;
	// 以物品单位重量价值递减序装入物品

	while ( i <= n && w[i] <= eleft )
	{
		eleft -= w[i];
		b += p[i];
		i++;
	}
	//装满背包，也就是找到第一个装不下的包

	if ( i <= n )
	{
		b += ( p[i]*1.0 / w[i] ) * eleft;
	}

	return b;
}

template< class Typew,class Typep >
void Knap< Typew,Typep >::Backtrack(int i)
{
	if ( i > n )
	{
		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 )
		//从i+1开始的所有符合条件的重量和，如果符合这个条件才去计算
	{
		Backtrack(i+1);
	}
}

class Object
{
	friend int Knapsack(int*,int*,int,int);
public:
	int operator<=(Object a) const
	{
		return ( d >= a.d );
	}
	int operator>(Object a) const
	{
		return (d<a.d);
	}
public:
	int ID;
	float d;
};

/*
我们上面提到先定位第一个数，然后整理这个数组，把比这个数小的放到它的左边，大的放右边，然后
返回这中间值的位置，下面这函数就是做这个的。
*/
//a[10],则 left = 0,right = 9;
int partition(Object n[],int left,int right)
{
	int lo,hi;
	Object pivot,t;
	pivot.d = n[left].d;
	pivot.ID = n[left].ID;
	cout<<pivot.d<<endl;
	cout<<pivot.ID<<endl;
	cout<<"start"<<endl;
	lo=left-1;
	hi=right+1;

	while(lo+1!=hi) 
	{
		cout<<"start compare"<<endl;
		cout<<"lo+1 = "<<lo+1<<endl;
		cout<<"hi = "<<hi<<endl;
		cout<<n[lo+1].d<<endl;
		cout<<n[lo+1].ID<<endl;
		cout<<n[hi-1].d<<endl;
		cout<<n[hi-1].ID<<endl;
		cout<<"end compare"<<endl;
		if(n[lo+1]<=pivot)
			lo++;
		//如果左边的数据小于中枢点
		else if(n[hi-1]>pivot)
			hi--;
		else 
		{
			cout<<"交换数据"<<endl;
			t.d = n[lo+1].d;
			t.ID = n[lo+1].ID;
			n[lo+1].d = n[hi-1].d;
			n[lo+1].ID = n[hi-1].ID;
			n[hi-1].d = t.d;
			n[hi-1].ID = t.ID;
			++lo;
			--hi;
			
		}
	}

	n[left].d = n[lo].d;
	n[left].ID = n[lo].ID;
	n[lo].d = pivot.d;
	n[lo].ID = pivot.ID;
	//要注意与n[left]交换的n[low]是n[high]的前一个数据
	return lo;
}
void quicksort(Object n[], int left,int right)
{
	int dp;
	if (left<right) 
	{

   	 /*
    	这就是下面要讲到的函数，按照上面所说的，就是把所有小于53的数放
    	到它的左边，大的放在右边，然后返回53在整理过的数组中的位置。
    	*/
    	dp=partition(n,left,right);

    	quicksort(n,left,dp-1);

    	quicksort(n,dp+1,right); //这两个就是递归调用，分别整理53左边的数组和右边的数组
	}
}

template<class Typew,class Typep >
Typep Knapsack( Typep p[],Typew w[],Typew c,int n)
{
	//为Knap::Backtrack初始化
	Typew W = 0;
	Typep P = 0;
	Object* Q = new Object[n+1];

	Q[0].ID =0;
	Q[0].d = 0;
	for ( int i = 1; i <= n; ++i )
	{
		Q[i].ID = i;
		Q[i].d = 1.0 * p[i] / w[i];
		cout<<Q[i].ID<<endl;
		cout<<Q[i].d<<endl;
		cout<<"the data:"<<endl;
		P += p[i];
		W += w[i];
	}

	if ( W <= c )
	{
		return P;
		//装入所有物品
	}
	//依物品单位重量价值排序
	//sort(Q,n);
	quicksort(Q,0,n);
	for ( i = 0; i <= n; ++i )
	{
		cout<<Q[i].ID<<endl;
		cout<<Q[i].d<<endl;
	}
	Knap< Typew,Typep > K;
	K.p = new Typep[n+1];
	K.w = new Typew[n+1];
	for ( i = 1; i <= n; ++i )
	{
		K.p[i] = p[Q[i-1].ID];
		K.w[i] = w[Q[i-1].ID];
		cout<<"asdf"<<endl;
		cout<<K.p[i]<<endl;
		cout<<K.w[i]<<endl;
	}

	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;
	cout<<"the bestp is: "<<K.bestp<<endl;
	return K.bestp;

}
int main()
{
	int n = 4;
	int c = 7;
	float w[5]={0,3,5,2,1};
	float p[5]={0,9,10,7,4};
	Knapsack<float,float>(p,w,c,n);

	return 0;
}