贪心法
简介
贪心算法也称贪婪算法，是指在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而可以得到结果是最好或最优的算法。
贪心算法一般用于解决最优子结构的问题，最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。而动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码，但是对于很多问题，只是选择当前最优的解可能会导致辛普森悖论（Simpson's Paradox），不一定最终是最优解。单由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。证明贪心算法是否最优解一般有两种方法，归纳法和反证法。如何证明其得出的解不是最优解也可以用这两种方法证明，当然也可与举出反例论证。
流程
步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来。
示例
硬币找零
贪心法的介绍我们引入一个场景，硬币找零问题，商家需要用硬币给用户找零，假如每种面值的硬币都无限多，同时用户不想要太多的零钱，那么如果才能使得找零的硬币个数最少？从贪心的角度，应该是先用最大额面值的硬币进行找零，需要找零的金额小于最大面额之后，再用次大面额进行找零，以此类推。这种思想就是贪心法，即每一步都用当前的最优解去解决问题。
商家需要用硬币给用户找零，假如每种面值的硬币都无限多，同时用户不想要太多的零钱，那么如果才能使得找零的硬币个数最少？
从贪心的角度，应该是先用最大额面值的硬币进行找零，需要找零的金额小于最大面额之后，再用次大面额进行找零。
C++实现
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
vector<int> Num{ 3,0,2,1,0,3,5 }, Value{ 1,2,5,10,20,50,100 };
vector<tuple<int, int> > BagsQues(int money) {
int sum = 0;
vector<tuple<int, int> > ch;
for (int i = Value.size() - 1; i >= 0; --i) {
int N = min(money / Value[i], Num[i]);
money = money - N * Value[i];
sum += N;
if (N != 0) {
ch.push_back({ Value[i], N });
}
if(money == 0)
return ch;
}
ch.clear();
ch.push_back({ -1, -1 });
return ch;
}
int main()
{
int money;
cin >> money;
vector<tuple<int, int> > m = BagsQues(money);
for (int i = 0; i < m.size(); ++i) {
cout << get<0>(m[i]) << ":" << get<1>(m[i]) << endl;
}
system("PAUSE");
return 0;
}
正确性证明
如果需要找零11，零钱的类型是7、5、1三种类型，用贪心法的思路是先找7元，然后剩余4元，只能用1元面额的硬币进行找零，最终是1+4=5个硬币，但是如果直接用2个5元和一个1元硬币找零，则只需要3个硬币。
我们可以用三种币值做一个简要说明，什么时候贪心算法在找零的时候是错误的，比如{1，15，25}的币值系统，25+1<15*2，所以30元的找零问题贪心场景下就不是最优解，再比如{1，8，20}，20+1<8*3，同样在24元的找零问题会出现badcase。
硬币找零一定不正确吗？也不一定，比如人民币的面额有1、2、5、10、20、50、100等7种面额，平时我们在找零的时候头脑中也基本是用贪心的方式进行运算的，这种找零时没有问题的。
所以这个问题上，贪心是否正确和面值的类型有关。如果要保证贪心算法的正确性，币值系统的步长不能特别长，否则很容易出现其他组合更优的情况。
最小生成树
设G = (V, E)是一个无向连通带权图，即一个网络。E的每条边(v, w)的权为c[v][w]。
如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。
生成树的各边权的总和称为该生成树的耗费。
在G的所有生成树中，耗费最小的生成树称为G的最小生成树MST(minimum spanning tree) 。
连通块是一组顶点以及边的集合，这些顶点可以通过边连通在一起。
首先定义两个点之间的距离为两个点之间边的权重，一个点到一个连通块的最小距离就是这个点到连通块中某个点的距离的最小值。
贪心的过程是任意选择一个点作为连通块，然后找到到这个连通块距离最小的点，把这个点以及对应的便加入连通块。
C++实现
// O(N^3)
#include
using namespace std;
//用邻接矩阵表示无向图
#define N 6 //节点个数
#define M 100000//最大值，表示不可达
int matrix[N][N]=
{
M,6,1,5,M,M,
6,M,5,M,3,M,
1,5,M,5,6,4,
5,M,5,M,M,2,
M,3,6,M,M,6,
M,M,4,2,6,M
};
void prim()
{
bool flag[N]; //标记某个点是否当前生成树集合中
int i,j;
//初始化集合
for(i = 0; i < N; ++i) flag[i] = false;
flag[0] = true;
int count = 1;
while(count++ < N)
{
int min = M;
int e1 = -1, e2 = -1;
for(i = 0; i < N; ++i)
{
if(flag[i])
{
for(j = 0; j < N; ++j)
{
if(!flag[j])
{
if(matrix[i][j] < min)
{
min = matrix[i][j];
e1 = i;
e2 = j;
}
}
}
}
}
cout << e1 + 1 << "-" << e2 + 1<<" "<< matrix[e1][e2] << endl;
flag[e2] = true;
}
}
int main(int argc, char* *argv)
{
prim();
system("pause");
return 0;
}
正确性证明