/*
有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為wi。最優裝載問題要求
確定，在裝載體積不受限制的情況下，應如何裝載才能將盡可能多的集裝箱裝上輪船。該
問題可形式化描述為：
max{xi之和}i從1-n
wixi之和<=c,xi屬于{0,1},1<=i<=n
其中xi=0,表示不裝入集裝箱i,xi=1表示裝入集裝箱i
*/

/*
算法描述：
采用重量最輕者先裝的貪心選擇策略
*/

template<class Type>
int  Partion( Type *d, int left, int right )
{
	int i,j;
	Type temp;
	Type less = d[left];
	i = left;
	j = right;
	while( i < j )
	{
		while( d[++i] < less );
		while( d[--j] > less );
		
		if ( i < j )
		{
			temp = d[i];
			d[i] = d[j];
			d[j] = temp;
		}	
	}
	d[left] = d[j];
	d[j] = less;
	return j;
}

template<class Type>
bool Sort( Type *d, int left,int right )
{
	if ( left < right )
	{
		int middle = Partion( d, left, right );
		Sort( d, left, middle - 1 );
		Sort( d, middle + 1, right );
	}
	return true;
}

template< class Type >
void Loading( int x[], Type w[], Type c, int n )
{
	int *t = new int[n+1];
	for( int i = 1; i <= n; ++i )
	{
		t[i] = w[i];
	}
	Sort(t,1,n);
	//，可采用遞歸方法實現排序
	for( i = 1; i <= n; ++i )
	{
		x[i] = 0;
	}

	for( int i = 1; i <= n && w[t[i]] <= c; ++i )
	{
		x[t[i]] = 1;
		c -= w[t[i]];
	}
}

/*
算法實現后要證明算法具有貪心選擇性質和最優子結構的性質：
證明最優裝載問題中有一個最優解是以貪心選擇開始的。
證明的思路也就是
（1）首先考察問題的一個整體最優解，并證明可以修改這個最優解，使其以貪心選擇開始。
（2）作了貪心選擇后，原問題簡化為一個規模更小的類似子問題。
（3）然后，用數學歸納法證明，通過每一步作貪心選擇，最終可以得到問題的
一個整體最優解。其中證明貪心選擇后的問題簡化為規模更小的類似子問題的關鍵在于利用
該問題的最優子結構性質。

設集裝箱已經依其重量從小到大排序，(x1,x2,...,xn)是最優裝載問題的一個最
優解。又設k是所有xi為1中的最小的i。所以，如果給定的最優裝載問題有解，則
1<=k<=n
（1）如果k=1，則{x1,..,xn}滿足貪心選擇性質
（2）如果k>1,取y1 = 1,yk = 0, yi = x,1<i<=n,i!=k
則有：wiyi總和(1<=i<=) = w1  + wixi總和(2<=i<=n) - wk
                      <= wixi總和(1<=i<=n) <= c
因此(y1,y2,...,yn)是所給最優裝載問題的一個可行解釋
另一方面 yi總和(1<=i<=n) = xi總和(1<=i<=n)，則(y1,y2,...,yn)
是一個滿足貪心選擇性質的最優解釋。所以最優裝載問題具有貪心選擇性質
*/

/*
最有子結構性質：
設(x1,x2,...xn)是最優裝載問題的一個滿足貪心算法的最優解，則易知
x1 = 1,(x2,...,xn)是輪船載重量為c-w1且待裝船集裝箱為{2,3,...,n}時相應
最優裝載問題的一個最優解，可用反證法證明，如果不是，與全局最優矛盾。
*/

int main()
{
	return 0;
}