#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;
}