贪心算法的基本要素.cpp

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

/*
贪心算法通过一系列的选择得到一个问题的解。它所作的每一个选择都是当前
状态下某种意义的最好选择，即贪心选择。希望通过每次所作的贪心选择导致
最终结果是问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下，
确能达到预期的目的。
*/
/*
我们怎么知道是否可用贪心算法来解此问题：
贪心选择性质和最优子结构性质
*/
/*
贪心选择性质：
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优得到，
即贪心选择得到。这是贪心算法的可行的第一个基本要素，也就是贪心算法与
动态规划算法的主要区别。
在动态规划算法中，每步所作的选择往往依赖于相关的子问题的解。因而只有在
解出相关子问题后，才能作出选择。而在贪心算法中，仅在当前状态下作出最好
选择，即局部最优选择。然后再去解出这个选择后产生的相应的子问题。贪心算法
所作的贪心选择可以依赖于以往所作过的选择，但绝不依赖于将来所做的选择，
也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各
子问题，而贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，
每作一次贪心选择就将所求问题简化为一个规模更小的子问题。

对于具体的问题，要确定它是否具有贪心选择性质，我们必须证明每一步所作的贪心
选择最终导致问题的一个整体最优解。通常可以用我们在证明活动安排问题的贪心
选择性质所采用的方法证明：
首先考察问题的一个整体最优解，并证明可以修改这个最优解，使其以贪心选择开始。
而且做了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法
证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。其中，证明，
贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构
性质。
*/
/*
最优子结构性质：
当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。
问题所具有的这个性质是该问题可以用动态规划算法或贪心算法求解的一个关键特征。
在活动安排问题中，其最优子结构性质表现为：若A是对于E的活动安排问题包含于
活动1的一个最优解，则相容活动集合A'=A-{1}是对于E'={i属于E:si>=f1}的活动安排
问题的一个最优解
*/

/*
贪心算法和动态规划算法的差异：
例如：
背包问题和0-1背包问题：
*/
//背包问题算法：
void Knapsack( int n, float M, float v[], float w[], float x[] )
{
	Sort( n, v, w );
	int i;
	for( int i = 1; i <= n; ++i )
	{
		x[i] = 0;
	}
	float c = M;
	for( int i = 1; i <= n; ++i )
	{
		if ( w[i] > c )
		{
			break;
		}
		x[i] = 1;
		c -= w[i];
	}
	if ( i <= n )
	{
		x[i] = c/w[i];
	}
}

/*
对于0-1背包问题，贪心选择之所以不能得到最优解，主要是不具有贪心选择性质，
应比较物品选择和不选择所导致的最终结果，然后再作出最好选择。因此依赖于将来的，
由此导致许多的重叠子问题。
*/