贪心算法

路漫 2020-05-07

当面对一个复杂的问题,需要求得问题最优解的时候,贪心法可以高效率的解决问题;

贪心法不是从整体最优考虑,它仅仅是通过一系列在局部看来最好的选择而得到问题整体的最优解

贪心法并不是对所有的问题都能得到最优解,但对许多问题它确实能产生整体最优解,而对一些问题即使不能得到整体最优解,也能得到最优解的近似解;

许多经典的算法都是用贪心法设计的,如,哈夫曼算法、Prim算法、Kruskal算法和Dijkstra算法等均是典型的贪心算法,都是利用贪心选择策略得到了问题的最优解;

适用贪心算法解决问题应具有如下两个重要性质:
  1、最优子结构性质,当问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质;
  2、贪心选择性质,所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择(贪心选择)来得到,即,每一步所作出的贪心选择最终可导致问题的整体最优解;

一、活动安排问题

设有n个活动的集合E = {E1,E2,...En},其中各活动需共享同一资源,每一活动Ei均有使用资源的时间要求,起始时间Si,结束时间Fi;若(Si,Fi)与(Sj,Fj)不相交,则活动Ei与Ej相容,资源的管理者只能选择彼此相容的活动进行安排;要求,在给定的活动中选择出最大相容活动子集合(活动个数最多),进行资源分配。

采用贪心选择策略求解问题,对于给定的n个活动{E1,E2,...En},贪心选择策略为:
  1、首选结束时间最早的活动Ei,保留与Ei相容的活动,剔除与Ei不相容的活动(活动按结束时间Fi非递减排序);
  2、在剩余活动中选择结束时间最早的活动Ej,保留与Ej相容的活动,剔除与Ej不相容的活动(通过活动的结束时间找下一个活动的开始时间,再通过活动的开始时间找下一个活动的结束时间);
  重复步骤2,直至全部活动处理完毕。

void GreedySelector(int n,int s[],int f[],bool A[])
{   /* A中保存选择结果 */
    A[1] = true;
    int j = 1;
    for (int i=2; i<=n; ++i)
    {
        if(s[i] >= f[j])
        {
            A[i] = true;
            j = i;
        }
        else
        {
            A[i] = false;
        }
    }
}

二、背包问题

给定n种物品和一个背包,已知背包的容量(载重量)为C及各物品的重量wi、价值vi,现求解如何选择装入背包的物品,使得背包中物品的总价值最大。

例,给定3种物品和背包,已知背包的容量为10,物品的重量wi = {6,5,5}  (物品均可拆分) ,价值vi = {30,20,15},现要求按背包问题求解,使得装入背包的物品总价值最大。 

背包问题可用贪心法求解:
  1、求每件物品的单位重量价值:Vi/Wi;
  2、按单位重量价值由高至低选装物品,直至装满包;

背包问题的解为{1,4/5,0},物品价值46

物品不可拆分的,不能用贪心法求解

相关推荐