算法--贪心

一：定义与概念
概念：每一步总是做出在当前看来最好的选择。
基本思路：
1 建立数学模型来描述问题。
2 把求解的问题分成若干个子问题。
3 对每一子问题求解，得到子问题的局部最优解。
4 把子问题的解局部最优解合成原来解问题的一个解。

贪心法存在的问题：
1 不能保证求得的最后解是最佳的；
2 不能用来求最大或最小解问题；
3 只能求满足某些约束条件的可行解的范围

贪心实现的一般流程

Greedy(C)  //C是问题的输入集合即候选集合
{
    S={ };  //初始解集合为空集
    while (not solution(S))  //集合S没有构成问题的一个解
    {
       x=select(C);    //在候选集合C中做贪心选择
       if feasible(S, x)  //判断集合S中加入x后的解是否可行
          S=S+{x};
          C=C-{x};
    }
   return S;

二：应用与实现
1:组合问题
1.1活动安排问题
1.2找零钱
1.3数字组合问题
1.4均分卡牌
1.5特殊背包问题
1.6小船过河问题
2：集合覆盖问题
2.1区间完全覆盖问题
2.2最大不相交覆盖问题
2.3区间选点问题
3：买卖交易问题
3.1考虑截止日期的买卖交易
3.2销售比赛问题
3.3部分股票问题
4：图里的问题
4.1哈夫曼编码
4.2最短路径问题
4.3最小生成树问题
4.4图着色问题
4.5TSP问题
4.6二分图最大匹配（匈牙利算法）
5.7二分图最佳匹配（KM算法）