枚举法与贪婪法

枚举法

在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法。枚举法是利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，因此枚举法是通过牺牲时间来换取答案的全面性。

使用枚举法解决问题时的主要思路：

  1. 确定枚举对象、范围和判定条件。

  2. 逐一枚举可能的解并验证每个解是否是问题的解。

最最重要的，就是第一步中确定范围的想法，在使用枚举法前，我们必须确保问题的可行解范围是能够被枚举的。也正因为需要遍历问题的可行解范围，我们常用循环结构来进行枚举。

以上机课中 列举100以内素数 的题目为例，一般解法的思路就是利用枚举的方法，将100以内的数全部遍历检查其是不是素数，若是素数就输出。

#include <iostream>

using namespace std;

int main()
{ 
  for (int i=1;i<=100;i++) {         //枚举1到100的数
    bool flag=true;              //是否素数的标志
    for (int j=2;j<i;j++) {          //枚举2到i-1的数
      //如果j整除i，则i不是素数，将标志修改为false，退出内层的循环
      if (i%j==0) {
        flag=false; 
        break;
      }
    }
    if (!flag) continue;         //如果标志为false，不输出
    cout << i << endl;
}

但枚举法的劣势也会在这个程序中显示出来，如果我们要求列出 1010内的所有素数，在用以上程序逻辑进行计算时，我们可能会进行1020量级次运算，这显然是不可接受的。

因此在使用枚举法时，我们必须注意到枚举法的性能是相对不好的，运算量比较大，效率不高。在编码中对性能的要求可能会迫使你更多的思考，选择其他算法或者使用一些小技巧来使得枚举效率更高（比如在枚举素数时，有只需要线性时间的欧拉筛算法）

贪婪法

贪婪法又称贪心算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择（局部最优解），从而希望导致结果是最好或最优的算法。

从上面这句对算法的整体描述，我们可以知道贪婪法保证的是每一步的局部最优解，但无法保证全局最优。如果需要用贪婪法得到全局最优解，那此问题必须是最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

之后我们会用例子让大家对贪婪法的局部最优和全局最优有一个直观的了解。下面是使用贪婪法的基本步骤：

  1. 从某个初始解出发

  2. 采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题规模。

  3. 将所有解综合起来

使用贪婪法的一个例子就是上课时提到的：对于一种货币，有面值为1分, 2分, 5分和1角的硬币，最少需要多少个硬币来找出K分钱的零钱。

我们使用贪婪法的思想就是不断地使用面值最大的硬币。如要找零的值小于最大的硬币值，则尝试第二大的硬币，依此类推。以下为示例代码。可以发现在这个问题中，使用贪婪法是有效的，能够找到全局最优解。

int main(){ 
	int money;
	int onefen = 0, twofen = 0, fivefen = 0, onejiao = 0;
	cout << "输入要找零的钱（以分为单位）：";
	cin >> money; 

 	//不断尝试每一种硬币 
	while (money >= 10) {onejiao++; money -= 10;}
	while (money >= 5) {fivefen++; money -= 5;}
	while (money >= 2) {twofen++; money -= 2;}
	while (money >= 1) {onefen++; money -= 1;}

 	//输出结果
	if(onejiao == 0 && onefen == 0 && twofen == 0 && fivefen == 0){
 		cout<<"无解";
	}else{
		cout << "1角硬币数：" << onejiao << endl;
		cout << "5分硬币数：" << fivefen << endl;
		cout << "2分硬币数：" << twofen << endl;
		cout << "1分硬币数：" << onefen << endl;
	}
	return 0;
}

但如果我们把问题条件稍作调整为 对于一种货币，有面值为1分, 3分, 9分和1角的硬币，最少需要多少个硬币来找出K分钱的零钱。

当K为12时，可以发现贪婪法已经失效，我们找到的不是最优解。那么如何在这种情况下找到全局最优解？可以使用动态规划算法。贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

在解决问题时，一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。但大多数问题都无法简单的用贪心法解决，需要构建更精准的算法逻辑。

当然，在一些工程问题中往往我们很难找到全局最优解（或者只需要一个局部最优解），这时由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。