贪心最优装载.cpp

算法分析中的贪心算法的实现

/*
有一批集装箱要装上一艘载重量为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;
}