精华内容
下载资源
问答
  • 贪心

    千次阅读 2018-04-03 21:10:38
    贪心的定义: 贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的...

    贪心的定义:

           贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择的性质,我们必须证明每一步所作的贪心选择最终能得到问题的最优解。

    最优子结构:

    当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响,而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择,不能回退;动态规划则会根据以前的选择结果对当前进行选择,有回退功能。动态规划主要运用于二维或三维问题,而贪心一般是一维问题 。

    例题:

    确实如此,世界杯来了,球迷的节日也来了,估计很多ACMer也会抛开电脑,奔向电视了。 
    作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目) 
     

    Input

    输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据Ti_s,Ti_e (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。 
     

    Output

    对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。
     

    Sample Input

    
        
    12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0
     

    Sample Output

    
        
    5

    解析:

        要看尽可能多的电视节目,首先需要尽可能的每时每刻都在看,而且还要考虑不能看那种时间特别长的节目,这会让我们因为一个节目而浪费许多时间,首先可以把节目的开始和结束时间存到一个结构体数组中,然后对结构体数组根据结束时间进行排序,然后从第一个节目开始看,如果下一个节目的开始时间早于上一个的结束时间,这个节目就不能看了,然后继续看下一个节目,如果下一个节目的开始时间晚于上一个的话,就可以看这一个节目,然后结束时间需要更新成这一个节目的结束时间。

    #include<iostream>
    #include <deque>
    #include<stack>
    #include<queue>
    #include<math.h>
    #include<algorithm>
    #include<stdlib.h>
    #include<string>
    #include<stdio.h>
    #include<string.h>
    typedef long long LL;
    #define $ 3.141592654
    using namespace std;
    struct W
    {
        int a,b;
    
    };
    bool cmp(struct W x,struct W y)
    {
        return x.b<y.b;
    }
    int main()
    {
        for(;;)
        {
            int n,i,j=1,k;
            struct W w[100];
            scanf("%d",&n);
            if(n==0)
                break;
            for(i=0;i<n;i++)
                scanf("%d%d",&w[i].a,&w[i].b);
            sort(w,w+n,cmp);
            k=w[0].b;
            for(i=1;i<n;i++)
            {
                if(w[i].a<k)
                    continue;
                else
                {
                    j++;
                    k=w[i].b;
                }
            }
            printf("%d\n",j);
    
        }
        return 0;
    }
    
    
    贪心最重要的一点就是“贪”,贪就是尽可能的获取一个最优的解,做题时首先要思考如何实现最优解。
    展开全文
  • 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法
  • 贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法
  • 贪心法 逆序问题

    2017-06-06 23:12:09
    贪心法求逆序问题代码
  • 贪心算法 贪心算法的理解 贪心算法的算法 贪心算法的讲解
  • 贪心_贪心_源码

    2021-10-04 12:16:59
    贪心相关程序,用于求解各类常见的贪心问题,能够有一个很好的收获
  • 贪心算法

    千次阅读 2018-05-08 20:25:41
    必须注意的是,贪心算法不是所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。 所以所采用的贪心策略一定要仔细分析其...

    引言

    所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
    贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
    所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

    最短路径问题

    问题描述

    给定一个有向图G=(V,E),s为V中一点,以s为起点,要确定从s出发到V中每一个其他定点的距离(距离的定义是最短路径对应的长度).

    Dijkstra算法

    算法步骤

    • 初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则 < u,v >正常有权值,若u不是v的出边邻接点,则 < u,v > 权值为∞

    • 从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)

    • 以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权

    • 重复步骤b和c直到所有顶点都包含在S中

    代码

    const int  MAXINT = 32767;
    const int MAXNUM = 10;
    int dist[MAXNUM];//表示距离
    int prev[MAXNUM];//记录每个顶点的前驱顶点(因为最短路径的唯一性,所以每个点的前驱元素都是唯一的)
    
    int A[MAXUNM][MAXNUM];
    
    void Dijkstra(int v0)
    {
        bool S[MAXNUM];                                  // 判断是否已存入该点到S集合中
          int n=MAXNUM;
        for(int i=1; i<=n;   i)
        {
            dist[i] = A[v0][i];
            S[i] = false;                                // 初始都未用过该点
            if(dist[i] == MAXINT)   //如果该点与源点之间无边 
                  prev[i] = -1;
            else 
                  prev[i] = v0;
         }
         dist[v0] = 0;
         S[v0] = true;   
        for(int i=2; i<=n; i  )
        {
             int mindist = MAXINT;
             int u = v0;                               // 找出当前未使用的点j的dist[j]最小值
             for(int j=1; j<=n;   j)
                if((!S[j]) && dist[j]<mindist)//如果j点没有被用过而且dist[j]小于mindist
                {
                      u = j;                             // u保存当前邻接点中距离最小的点的号码 
                      mindist = dist[j];
                }
             S[u] = true; //将u置为已用
             for(int j=1; j<=n; j  )//更新u加入已用集合后的未用顶点集合中点到已用集合中点的距离
                 if((!S[j]) && A[u][j]<MAXINT)
                 {
                     if(dist[u]   A[u][j] < dist[j])     //在通过新加入的u点路径找到离v0点更短的路径  
                     {
                         dist[j] = dist[u]   A[u][j];    //更新dist 
                         prev[j] = u;                    //记录前驱顶点 
                      }
                  }
         }
    }

    算法复杂度

    算法的时间复杂度是senta(n^2)

    稠图的线性时间算法

    最小耗费生成树

    问题描述

    设G = (V,E)是无向连通带权图,即一个网络。E中的每一条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树。
    最小生成树最常见的题就是求解n个城市之间的修路问题.

    Kruskal算法

    算法描述

    给定无向连同带权图G = (V,E),V = {1,2,…,n}。Kruskal算法构造G的最小生成树的基本思想是:

    • 将G的n个顶点看成n个孤立的连通分支,将所有的边按权从小大排序。

    • 从第一条边开始,依边权递增的顺序检查每一条边。并按照下述方法连接两个不同的连通分支:当查看到第k条边(v,w)时,如果端点v和w分别是当前两个不同的连通分支T1和T2的端点时,就用边(v,w)将T1和T2连接成一个连通分支,然后继续查看第k 1条边;如果端点v和w在当前的同一个连通分支中,就直接再查看k 1条边。这个过程一个进行到只剩下一个连通分支时为止。

    此时,已构成G的一棵最小生成树。

    代码实现

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    #define maxn 110    //最多点个数
    int n, m;   //点个数,边数
    int parent[maxn];   //父亲节点,当值为-1时表示根节点
    int ans;    //存放最小生成树权值
    struct eage     //边的结构体,u、v为两端点,w为边权值
    {
        int u, v, w;
    }EG[5010];
    
    bool cmp(eage a, eage b)    //排序调用
    {
        return a.w < b.w;
    }
    
    int Find(int x)     //寻找根节点,判断是否在同一棵树中的依据
    {
        if(parent[x] == -1) return x;
        return Find(parent[x]);
    }
    
    void Kruskal()      //Kruskal算法,parent能够还原一棵生成树,或者森林
    {
        memset(parent, -1, sizeof(parent));
        sort(EG 1, EG m 1, cmp);    //按权值将边从小到大排序
        ans = 0;
        for(int i = 1; i <= m; i  )     //按权值从小到大选择边
        {
            int t1 = Find(EG[i].u), t2 = Find(EG[i].v);
            if(t1 != t2)    //若不在同一棵树种则选择该边,合并两棵树
            {
                ans  = EG[i].w;
                parent[t1] = t2;
            }
        }
    }

    复杂度分析

    当图的边数为e时,Kruskal算法所需的时间是O(eloge).

    Prim算法

    算法描述

    设G = (V,E)是连通带权图,V = {1,2,…,n}。构造G的最小生成树,Prim算法的基本思想是:首先置S = {1},然后,只要S是V的真子集,就进行如下的贪心选择:选取满足条件i ∈S,j ∈V – S,且c[i][j]最小的边,将顶点j添加到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

    代码实现

    /* Prim算法生成最小生成树  */
    void MiniSpanTree_Prim(MGraph MG)
    {
        int min, i, j, k;
        int adjvex[MAXVEX];/* 保存相关顶点的父亲节点 */
        int lowcost[MAXVEX];/* 保存相关顶点间边的权值 */
        lowcost[0] = 0;/* 初始化第一个权值为0,即v0加入生成树 */
        /* lowcost的值为0,在这里就是此下标的顶点已经加入生成树 */
        adjvex[0] = 0;/* 初始化第一个顶点下标为0 */
        cout << "最小生成树的边为:" << endl;
        for (i = 1; i < MG.numVertexes; i  )
        {
            lowcost[i] = MG.arc[0][i];/* 将v0顶点与之有边的权值存入数组 */
            adjvex[i] = 0;/* 初始化都为v0的下标 */
        }
    
        for (i = 1; i < MG.numVertexes; i  )
        {
            min = INFINITY; /* 初始化最小权值为∞, */
    
            j = 1;
            k = 0;
    
            while (j < MG.numVertexes)/* 循环全部顶点 */
            {
                if (lowcost[j] != 0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
                {
                    min = lowcost[j];/* 则让当前权值成为最小值 */
                    k = j;/* 将当前最小值的下标存入k */
                }
    
                j  ;
            }
    
            cout << "(" << adjvex[k] << ", " << k << ")" << "  "; /* 打印当前顶点边中权值最小的边 */
            lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
    
            for (j = 1; j < MG.numVertexes; j  )/* 循环所有顶点 */
            {
                /* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
                if (lowcost[j] != 0 && MG.arc[k][j] < lowcost[j])
                {
                    lowcost[j] = MG.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
                    adjvex[j] = k;/* 将k设为下标j的父亲节点 */
                }
            }
        }
        cout << endl;
    }

    复杂度分析

    此算法的时间复杂度为O(n^2)

    总结

    当e = Ω(n^2)时,Kruskal算法比Prim算法差;
    但当e = o(n^2)时,Kruskal算法比Prim算法好得多。

    展开全文
  • 贪心_贪心算法_源码

    2021-10-03 06:31:34
    大一新手之贪心算法观赏练习,适合初学者使用!内含PPT和例题,请配合食用
  • 贪心算法贪心算法贪心算法贪心算 背包问题背包问题背包问题
  • 贪心

    千次阅读 2016-11-28 14:20:25
    贪心法又称贪婪法, 在问题求解时,总是做出在当前看来是最好的选择,或者说是:总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。

    贪心法(Greedy Approach)又称贪婪法, 在对问题求解时,总是做出在当前看来是最好的选择,或者说是:总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。


    贪心法的设计思想

    当一个问题具有以下的性质时可以用贪心算法求解:每一步的局部最优解,同事也说整个问题的最优解。

    如果一个问题可以用贪心算法解决,那么贪心通常是解决这个问题的最好的方法。 贪婪算法一般比其他方法例如动态规划更有效。但是贪婪算法不能总是被应用。例如,部分背包问题可以使用贪心解决,但是不能解决0-1背包问题。

    贪婪算法有时也用用来得到一个近似优化问题。例如,旅行商问题是一个NP难问题。贪婪选择这个问题是选择最近的并且从当前城市每一步。这个解决方案并不总是产生最好的最优解,但可以用来得到一个近似最优解。

    让我们考虑一下任务选择的贪婪算法的问题, 作为我们的第一个例子。问题:

    给出n个任务和每个任务的开始和结束时间。找出可以完成的任务的最大数量,在同一时刻只能做一个任务。

    例子:

    下面的6个任务:
         start[]  =  {1, 3, 0, 5, 8, 5};
         finish[] =  {2, 4, 6, 7, 9, 9};
    最多可完成的任务是:
     {0, 1, 3, 4}

    贪婪的选择是总是选择下一个任务的完成时间至少在剩下的任务和开始时间大于或等于以前选择任务的完成时间。我们可以根据他们的任务完成时间,以便我们总是认为下一个任务是最小完成时间的任务。

    • 1)按照完成时间对任务排序
    • 2)选择第一个任务排序数组元素和打印。
    • 3) 继续以下剩余的任务排序数组。

    ……a)如果这一任务的开始时间大于先前选择任务的完成时间然后选择这个任务和打印。

    在接下来的C程序,假设已经根据任务的结束时间排序。

    #include<stdio.h>
    // 打印可以完成的最大数量的任务
    //  n   -->  所有任务的数量
    //  s[] -->  开始时间
    //  f[] -->  结束时间
    void printMaxActivities(int s[], int f[], int n)
    {
        int i, j;
        printf ("Following activities are selected \n");
        // 选择第一个任务
        i = 0;
        printf("%d ", i);
        //考虑剩下的任务
        for (j = 1; j < n; j++)
        {
          // 如果当前的任务开始比 前一个选择的任务结束时间大或相等,就选择它
          if (s[j] >= f[i])
          {
              printf ("%d ", j);
              i = j;
          }
        }
    }
    
    // driver program to test above function
    int main()
    {
        int s[] =  {1, 3, 0, 5, 8, 5};
        int f[] =  {2, 4, 6, 7, 9, 9};
        int n = sizeof(s)/sizeof(s[0]);
        printMaxActivities(s, f, n);
        getchar();
        return 0;
    }

    输出:

    Following activities are selected
    0 1 3 4

    贪心算法的基本要素

    对于一个具体的问题,怎么知道是否可用贪心算法解此问题,以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。

    但是,从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质:贪心选择性质和最优子结构性质。

    • 1、贪心选择性质

    所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。

    动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。

    对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。

    • 2、最优子结构性质

    当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

    • 3、贪心算法与动态规划算法的差异

    贪心算法和动态规划算法都要求问题具有最优子结构性质,这是2类算法的一个共同点。但是,对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题,并以此说明贪心算法与动态规划算法的主要差别。

    0-1背包问题:
    给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

    在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。

    背包问题:
    与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1 <= i <= n。

    这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而0-1背包问题却不能用贪心算法求解。

    用贪心算法解背包问题的基本步骤:

    • 首先计算每种物品单位重量的价值 Vi/Wi
    • 然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。
    • 若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。
    • 依此策略一直地进行下去,直到背包装满为止。

    伪代码:

    void Knapsack(int n,float M,float v[],float w[],float x[])
    {
      Sort(n,v,w);
      int i;
      for (i = 1 ; i <= n ; i++) 
        x[i] = 0;
        float c=M;
        for (i=1;i<=n;i++) {
          if (w[i] > c) break;
        }
        x[i]=1;
        c-=w[i];
      }
      if (i <= n) 
        x[i]=c / w[i];
    }

    算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此,算法的计算时间上界为 O(nlogn)。

    为了证明算法的正确性,还必须证明背包问题具有贪心选择性质。

    对于0-1背包问题,贪心选择之所以不能得到最优解是因为在这种情况下,它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。事实上,在考虑0-1背包问题时,应比较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此,动态规划算法的确可以有效地解0-1背包问题。


    贪心法的典型应用

    活动安排问题

    问题描述:设有 n 个活动的集合E={1,2,,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活 i 都有一个要求使用该资源的起始时间si和一个结束时间 fi ,且 si<fi 。如果选择了活动i,则它在半开时间区间 [si,fi) 内占用资源。若区间 [si,fi) 与区间 [sj,fj) 不相交,则称活动 i 与活动j是相容的。也就是说,当 si>=fj sj>=fi 时,活动 i 与活动j相容。

    由于输入的活动以其完成时间的非减序排列,所以算法 greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。

    算法 greedySelector 的效率极高。当输入的活动已按结束时间的非减序排列,算法只需 O(n) 的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用 O(nlogn) 的时间重排。

    例:设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:

    i1234567891011
    S[i]130535688212
    f[i]4567891011121314

    算法 greedySelector 的计算过程如下图所示[图来源网络]。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动,而空白长条表示的活动是当前正在检查相容性的活动。
    这里写图片描述

    若被检查的活动i的开始时间 Si 小于最近选择的活动 j 的结束时间fi,则不选择活动 i ,否则选择活动i加入集合 A 中。

    贪心算法并不总能求得问题的整体最优解。但对于活动安排问题,贪心算法greedySelector却总能求得的整体最优解,即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。

    活动安排问题实现:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std ;
    
    struct ActivityTime
    {
    public:
        ActivityTime (int nStart, int nEnd) 
            : m_nStart (nStart), m_nEnd (nEnd) 
        { }
        ActivityTime ()
            : m_nStart (0), m_nEnd (0)
        { }
        friend 
        bool operator < (const ActivityTime& lth, const ActivityTime& rth) 
        {
            return lth.m_nEnd < lth.m_nEnd ;
        }
    public:
        int m_nStart ;
        int m_nEnd ;
    } ;
    
    class ActivityArrange 
    {
    public:
        ActivityArrange (const vector<ActivityTime>& vTimeList) 
        {
            m_vTimeList = vTimeList ;
            m_nCount = vTimeList.size () ;
            m_bvSelectFlag.resize (m_nCount, false) ;
        }
        // 活动安排
        void greedySelector () 
        {
            __sortTime () ;
            // 第一个活动一定入内
            m_bvSelectFlag[0] = true ;    
            int j = 0 ;
            for (int i = 1; i < m_nCount ; ++ i) {
                if (m_vTimeList[i].m_nStart > m_vTimeList[j].m_nEnd) {
                    m_bvSelectFlag[i] = true ;
                    j = i ;
                }
            }
    
            copy (m_bvSelectFlag.begin(), m_bvSelectFlag.end() ,ostream_iterator<bool> (cout, ” “));
            cout << endl ;
        }
    
    private:
        // 按照活动结束时间非递减排序
        void __sortTime () 
        {
            sort (m_vTimeList.begin(), m_vTimeList.end()) ;
            for (vector<ActivityTime>::iterator ite = m_vTimeList.begin() ;
                    ite != m_vTimeList.end() ; 
                    ++ ite) {
                cout << ite->m_nStart << “, “<< ite ->m_nEnd << endl ;
            }
        }
    
    private:
        vector<ActivityTime>    m_vTimeList ;    // 活动时间安排列表
        vector<bool>            m_bvSelectFlag ;// 是否安排活动标志
        int    m_nCount ;    // 总活动个数
    } ;
    
    int main()
    {
        vector<ActivityTime> vATimeList ;
        vATimeList.push_back (ActivityTime(1, 4)) ;
        vATimeList.push_back (ActivityTime(3, 5)) ;
        vATimeList.push_back (ActivityTime(0, 6)) ;
        vATimeList.push_back (ActivityTime(5, 7)) ;
        vATimeList.push_back (ActivityTime(3, 8)) ;
        vATimeList.push_back (ActivityTime(5, 9)) ;
        vATimeList.push_back (ActivityTime(6, 10)) ;
        vATimeList.push_back (ActivityTime(8, 11)) ;
        vActiTimeList.push_back (ActivityTime(8, 12)) ;
        vATimeList.push_back (ActivityTime(2, 13)) ;
        vATimeList.push_back (ActivityTime(12, 14)) ;
    
        ActivityArrange aa (vATimeList) ;
        aa.greedySelector () ;
        return 0 ;
    }

    最优前缀码

    Huffman 编码是一种无损压缩技术。它分配可变长度编码不同的字符。贪婪的选择是分配一点代码最常见的字符长度。哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。

    给出现频率高的字符较短的编码,出现频率较低的字符以较长的编码,可以大大缩短总码长。

    _abcdef
    频率(千次)4513121695
    定长码000001010011100101
    变长码010110011111011100

    定长码: 3(45+13+12+16+9+5)=300 千位
    变长码: 145+313+312+316+49+45224 千位

    1、前缀码

    对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。

    编码的前缀性质可以使译码方法非常简单。

    表示最优前缀码的二叉树总是一棵完全二叉树,即树中任一结点都有2个儿子结点。

    平均码长定义为:

    B(T)=cCf(c)dT(c)

    其中, f(c) 表示字符c出现的概率, dt(c) 表示c的码长.使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。

    2、构造哈夫曼编码

    哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。

    算法以 |C| 个叶结点开始,执行 |C|1 次的“合并”运算后产生最终所要求的树 T

    f为键值的优先队列 Q 用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后,产生一棵新的树,其频率为合并的2棵树的频率之和,并将新树插入优先队列Q。经过n1次的合并后,优先队列中只剩下一棵树,即所要求的树T。

    算法 huffmanTree 用最小堆实现优先队列Q。初始化优先队列需要 O(n) 计算时间,由于最小堆的 removeMin put 运算均需 O(logn) 时间, n1 次的合并总共需要 O(nlogn) 计算时间。因此,关于 n 个字符的哈夫曼算法的计算时间为O(nlogn)

    3、哈夫曼算法的正确性

    要证明哈夫曼算法的正确性,只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。

    • (1)贪心选择性质
    • (2)最优子结构性质

    实现代码(Code highlighting produced by Actipro CodeHighlighter )

    #include <iostream>
    #include <vector>
    #include <queue> 
    using namespace std ;
    
    
    class HaffmanNode
    {
    public:
        HaffmanNode (int nKeyValue, 
                    HaffmanNode* pLeft = NULL,
                    HaffmanNode* pRight = NULL)
        { 
            m_nKeyValue = nKeyValue ;
            m_pLeft = pLeft ;
            m_pRight = pRight ;
        }
    
        friend 
        bool operator < (const HaffmanNode& lth, const HaffmanNode& rth)
        {
            return lth.m_nKeyValue < rth.m_nKeyValue ;
        }
    
    public:
        int        m_nKeyValue ;    
        HaffmanNode*    m_pLeft ;
        HaffmanNode*    m_pRight ;
    } ;
    
    class HaffmanCoding
    {
    public:
        typedef priority_queue<HaffmanNode*> MinHeap ;
        typedef HaffmanNode*    HaffmanTree ;
    
    public:
        HaffmanCoding (const vector<int>& weight) 
            : m_pTree(NULL)
        {
            m_stCount = weight.size () ;
            for (size_t i = 0; i < weight.size() ; ++ i) {
                m_minheap.push (new HaffmanNode(weight[i], NULL, NULL)) ;
            }
        }
        ~ HaffmanCoding()
        {
            __destroy (m_pTree) ;
        }
    
        // 按照左1右0编码 
        void doHaffmanCoding ()
        {
            vector<int> vnCode(m_stCount-1) ;
            __constructTree () ;
            __traverse (m_pTree, 0, vnCode) ;
        }
    
    private:
        void __destroy(HaffmanTree& ht) 
        {
            if (ht->m_pLeft != NULL) {
                __destroy (ht->m_pLeft) ;
            }
            if (ht->m_pRight != NULL) {
                __destroy (ht->m_pRight) ;
            }
            if (ht->m_pLeft == NULL && ht->m_pRight == NULL) {
                // cout << "delete" << endl ;
                delete ht ;
                ht = NULL ;
            }
        }
        void __traverse (HaffmanTree ht,int layers, vector<int>& vnCode) 
        {
            if (ht->m_pLeft != NULL) {
                vnCode[layers] = 1 ;
                __traverse (ht->m_pLeft, ++ layers, vnCode) ;
                -- layers ;
            }
            if (ht->m_pRight != NULL) {
                vnCode[layers] = 0 ;
                __traverse (ht->m_pRight, ++ layers, vnCode) ;
                -- layers ;
            }
            if (ht->m_pLeft == NULL && ht->m_pRight == NULL) {
                cout << ht->m_nKeyValue << " coding:  " ;
                for (int i = 0; i < layers; ++ i) {
                     cout << vnCode[i] << " " ;
                }
                cout << endl ;
            }
        }
    
        void __constructTree ()
        {
            size_t i = 1 ;
            while (i < m_stCount) {
                HaffmanNode* lchild = m_minheap.top () ;
                m_minheap.pop () ;
                HaffmanNode* rchild = m_minheap.top () ;
                m_minheap.pop () ;
    
                // 确保左子树的键值大于有子树的键值
                if (lchild->m_nKeyValue < rchild->m_nKeyValue) {
                    HaffmanNode* temp = lchild ;
                    lchild = rchild ;
                    rchild = temp ;
                }
                // 构造新结点
                HaffmanNode* pNewNode = 
                    new HaffmanNode (lchild->m_nKeyValue + rchild->m_nKeyValue,
                    lchild, rchild ) ;
                m_minheap.push (pNewNode) ;
                ++ i ;
            }
            m_pTree = m_minheap.top () ;
            m_minheap.pop () ;
        }
    
    private:
        vector<int> m_vnWeight ;    // 权值
        HaffmanTree m_pTree ;
        MinHeap        m_minheap ;
        size_t        m_stCount ;        // 叶结点个数
    } ;
    
    
    int main()
    {    
        vector<int> vnWeight ;
        vnWeight.push_back (45) ;
        vnWeight.push_back (13) ;
        vnWeight.push_back (12) ;
        vnWeight.push_back (16) ;
        vnWeight.push_back (9) ;
        vnWeight.push_back (5) ;
    
        HaffmanCoding hc (vnWeight) ;
        hc.doHaffmanCoding () ;
        return 0 ;
    }

    单源最短路径

    给定带权有向图 G=(V,E) ,其中每条边的权是非负实数。另外,还给定 V 中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

    1、算法基本思想

    Dijkstra算法是解单源最短路径问题的贪心算法。

    其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

    初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组dist作必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。

    例如,对下图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。

    这里写图片描述

    Dijkstra算法的迭代过程:

    迭代 s u dist[2] dist[3] dist[4] dist[5]
    初始 {1} - 10 maxint 30 100
    1 {1,2} 2 10 60 30 100
    2 {1,2,4} 4 10 50 30 90
    3 {1,2,4,3} 3 10 50 30 60
    4 {1,2,4,3,5} 5 10 50 30 60

    2、算法的正确性和计算复杂性

    (1)贪心选择性质
    (2)最优子结构性质
    (3)计算复杂性

    对于具有n个顶点和e条边的带权有向图,如果用带权邻接矩阵表示这个图,那么Dijkstra算法的主循环体需要 O(n) 时间。这个循环需要执行 n1 次,所以完成循环需要 O(n) 时间。算法的其余部分所需要时间不超过 O(n2)

    实现:

    #include <iostream>
    #include <vector>
    #include <limits>
    using namespace std ;
    
    class BBShortestDijkstra
    {
    public:
        BBShortestDijkstra (const vector<vector<int> >& vnGraph) 
            :m_cnMaxInt (numeric_limits<int>::max()) 
        {
            m_vnGraph = vnGraph ;
            m_stCount = vnGraph.size () ;
            m_vnDist.resize (m_stCount) ;
            for (size_t i = 0; i < m_stCount; ++ i) {
                m_vnDist[i].resize (m_stCount) ;
            }
        }
    
        void doDijkatra ()
        {
            int nMinIndex = 0 ;
            int nMinValue = m_cnMaxInt ;
            vector<bool> vbFlag (m_stCount, false) ;
            for (size_t i = 0; i < m_stCount; ++ i) {
                m_vnDist[0][i] = m_vnGraph[0][i] ;
                if (nMinValue > m_vnGraph[0][i]) {
                    nMinValue = m_vnGraph[0][i] ;
                    nMinIndex = i ;
                }
            }
    
            vbFlag[0] = true ;
            size_t k = 1 ;
            while (k < m_stCount) {
                vbFlag[nMinIndex] = true ;
                for (size_t j = 0; j < m_stCount ; ++ j) {
                    // 没有被选择
                    if (!vbFlag[j] && m_vnGraph[nMinIndex][j] != m_cnMaxInt ) {
                        if (m_vnGraph[nMinIndex][j] + nMinValue
                            < m_vnDist[k-1][j]) {
                            m_vnDist[k][j] = m_vnGraph[nMinIndex][j] + nMinValue ;
                        }
                        else {
                            m_vnDist[k][j] = m_vnDist[k-1][j] ;
                        }
                    }
                    else {
                        m_vnDist[k][j] = m_vnDist[k-1][j] ;
                    }
                }
                nMinValue = m_cnMaxInt ;
                for (size_t j = 0; j < m_stCount; ++ j) {
                    if (!vbFlag[j] && (nMinValue > m_vnDist[k][j])) {
                        nMinValue = m_vnDist[k][j] ;
                        nMinIndex = j ;
                    }
                }
                ++ k ;
            }
    
            for (int i = 0; i < m_stCount; ++ i) {
                for (int j = 0; j < m_stCount; ++ j) {
                    if (m_vnDist[i][j] == m_cnMaxInt) {
                        cout << "maxint " ;
                    }
                    else {
                        cout << m_vnDist[i][j] << " " ;
                    }
                }
                cout << endl ;
            }
        }
    private:  
        vector<vector<int> >    m_vnGraph ;
        vector<vector<int> >    m_vnDist ;
        size_t m_stCount ;
        const int m_cnMaxInt ;
    } ;
    
    int main()
    {
        const int cnCount = 5 ;
        vector<vector<int> > vnGraph (cnCount) ;
        for (int i = 0; i < cnCount; ++ i) {
            vnGraph[i].resize (cnCount, numeric_limits<int>::max()) ;
        }
        vnGraph[0][1] = 10 ;
        vnGraph[0][3] = 30 ;
        vnGraph[0][4] = 100 ;
        vnGraph[1][2] = 50 ;
        vnGraph[2][4] = 10 ;
        vnGraph[3][2] = 20 ;
        vnGraph[3][4] = 60 ;
    
        BBShortestDijkstra bbs (vnGraph) ;
        bbs.doDijkatra () ;
    }

    最小生成树

    G=(V,E) 是无向连通带权图,即一个网络。E中的每一条边 v,w 的权为 c[v][w] 。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树。最小生成树的性质:设G = (V,E)是连通带权图,U是V的真子集。如果(u,v)∈E,且u∈U,v∈V-U,且在所有这样的边中,(u,v)的权c[u][v]最小,那么一定存在G的一棵最小生成树,它意(u,v)为其中一条边。这个性质有时也称为MST性质。

    构造最小生成树的两种方法:Prim算法和Kruskal算法。Kruskal最小生成树(MST):在Kruskal算法中,我们通过逐个的选取最优边来获得一个MST。每次选择最小权重并且不构成环的边。Prim小生成树算法:在prim算法中,我们也是逐个的选取最优边来获得一个MST。我们维持两组:已经包含在MST的顶点和顶点的集合不包括在内的。贪婪的选择是选择最小的重量边缘连接两组。

    Prim算法

    设G = (V,E)是连通带权图,V = {1,2,…,n}。构造G的最小生成树Prim算法的基本思想是:首先置S = {1},然后,只要S是V的真子集,就进行如下的贪心选择:选取满足条件i ∈S,j ∈V – S,且c[i][j]最小的边,将顶点j添加到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

    如下带权图:
    这里写图片描述

    生成过程:

    1 -> 3 : 1
    3 -> 6 : 4
    6 -> 4: 2
    3 -> 2 : 5
    2 -> 5 : 3

    实现:

    /* 最小生成树(Prim)*/
    
    #include <iostream>
    #include <vector>
    #include <limits>
    using namespace std ;
    
    struct TreeNode
    {
    public:
        TreeNode (int nVertexIndexA = 0, int nVertexIndexB = 0, int nWeight = 0)
            : m_nVertexIndexA (nVertexIndexA),
            m_nVertexIndexB (nVertexIndexB),
            m_nWeight (nWeight)
        { }
    public:
        int m_nVertexIndexA ;
        int m_nVertexIndexB ;
        int m_nWeight ;
    } ;
    
    class MST_Prim
    {
    public:
        MST_Prim (const vector<vector<int> >& vnGraph) 
        {
            m_nvGraph = vnGraph ;
            m_nNodeCount = (int)m_nvGraph.size () ;
        }
        void DoPrim ()
        {
            // 是否被访问标志
            vector<bool> bFlag (m_nNodeCount, false) ;
            bFlag[0] = true ;
    
            int nMaxIndexA ;
            int nMaxIndexB ;
            int j = 0 ;
            while (j < m_nNodeCount - 1) {
                int nMaxWeight = numeric_limits<int>::max () ;
                // 找到当前最短路径
                int i = 0 ;
                while (i < m_nNodeCount) {
                    if (!bFlag[i]) {
                        ++ i ;
                        continue ;
                    }
                    for (int j = 0; j < m_nNodeCount; ++ j) {
                        if (!bFlag[j] && nMaxWeight > m_nvGraph[i][j]) {
                            nMaxWeight = m_nvGraph[i][j] ;
                            nMaxIndexA = i ;
                            nMaxIndexB = j ;
                        } 
                    }
                    ++ i ;
                }
                bFlag[nMaxIndexB] = true ;
                m_tnMSTree.push_back (TreeNode(nMaxIndexA, nMaxIndexB, nMaxWeight)) ;
                ++ j ;
            }
            // 输出结果
            for (vector<TreeNode>::const_iterator ite = m_tnMSTree.begin() ;
                    ite != m_tnMSTree.end() ;
                    ++ ite ) {
                cout << (*ite).m_nVertexIndexA << "->" 
                    << (*ite).m_nVertexIndexB << " : "
                    << (*ite).m_nWeight << endl ;
            }
        }
    private:
        vector<vector<int> > m_nvGraph ;    // 无向连通图
        vector<TreeNode>    m_tnMSTree ;    // 最小生成树
        int    m_nNodeCount ;
    } ;
    
    int main()
    {
        const int cnNodeCount = 6 ;
        vector<vector<int> > graph (cnNodeCount) ;
        for (size_t i = 0; i < graph.size() ; ++ i) {
            graph[i].resize (cnNodeCount, numeric_limits<int>::max()) ;
        }
        graph[0][1]= 6 ;
        graph[0][2] = 1 ;
        graph[0][3] = 5 ;
        graph[1][2] = 5 ;
        graph[1][4] = 3 ;
        graph[2][3] = 5 ;
        graph[2][4] = 6 ;
        graph[2][5] = 4 ;
        graph[3][5] = 2 ;
        graph[4][5] = 6 ;
    
        graph[1][0]= 6 ;
        graph[2][0] = 1 ;
        graph[3][0] = 5 ;
        graph[2][1] = 5 ;
        graph[4][1] = 3 ;
        graph[3][2] = 5 ;
        graph[4][2] = 6 ;
        graph[5][2] = 4 ;
        graph[5][3] = 2 ;
        graph[5][4] = 6 ;
    
        MST_Prim mstp (graph) ;
        mstp.DoPrim () ;
         return 0 ;
    }

    Kruskal算法

    当图的边数为e时,Kruskal算法所需的时间是O(eloge)。当 e=Ω(n2) 时,Kruskal算法比Prim算法差;但当 e=o(n2) 时,Kruskal算法比Prim算法好得多。给定无向连同带权图 G=(V,E) , V={1,2,,n} 。Kruskal算法构造G的最小生成树的基本思想是:

    (1)首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小大排序。
    (2)从第一条边开始,依边权递增的顺序检查每一条边。并按照下述方法连接两个不同的连通分支:当查看到第k条边(v,w)时,如果端点v和w分别是当前两个不同的连通分支T1和T2的端点是,就用边(v,w)将T1和T2连接成一个连通分支,然后继续查看第k+1条边;如果端点v和w在当前的同一个连通分支中,就直接再查看k+1条边。这个过程一个进行到只剩下一个连通分支时为止。

    此时,已构成G的一棵最小生成树。

    Kruskal算法的选边过程:

    1 -> 3 : 1
    4 -> 6 : 2
    2 -> 5 : 3
    3 -> 4 : 4
    2 -> 3 : 5

    实现:

    /* Kruskal算法)*/
    
    #include <iostream>
    #include <vector>
    #include <queue>
    #include <limits>
    using namespace std ;
    
    struct TreeNode
    {
    public:
        TreeNode (int nVertexIndexA = 0, int nVertexIndexB = 0, int nWeight = 0)
            : m_nVertexIndexA (nVertexIndexA),
            m_nVertexIndexB (nVertexIndexB),
            m_nWeight (nWeight)
        { }
        friend 
        bool operator < (const TreeNode& lth, const TreeNode& rth) 
        {
            return lth.m_nWeight > rth.m_nWeight ;
        }
    
    public:
        int m_nVertexIndexA ;
        int m_nVertexIndexB ;
        int m_nWeight ;
    } ;
    
    //  并查集
    class UnionSet 
    {
    public:
        UnionSet (int nSetEleCount)
            : m_nSetEleCount (nSetEleCount)
        {
            __init() ;
        }
        // 合并i,j。如果i,j同在集合中,返回false。否则返回true
        bool Union (int i, int j)
        {
            int ifather = __find (i) ;
            int jfather = __find (j) ;
            if (ifather == jfather )
            {
                return false ;
                // copy (m_nvFather.begin(), m_nvFather.end(), ostream_iterator<int> (cout, " "));
                // cout << endl ;
            }
            else
            {
                m_nvFather[jfather] = ifather ;
                // copy (m_nvFather.begin(), m_nvFather.end(), ostream_iterator<int> (cout, " "));
                // cout << endl ;
                return true ;
            }
    
        }
    
    private:
        // 初始化并查集
        int __init()
        {
            m_nvFather.resize (m_nSetEleCount) ;
            for (vector<int>::size_type i = 0 ;
                i < m_nSetEleCount;
                ++ i )
            {
                m_nvFather[i] = static_cast<int>(i) ;
                // cout << m_nvFather[i] << " " ;
            }
            // cout << endl ;
            return 0 ;
        }
        // 查找index元素的父亲节点 并且压缩路径长度 
        int __find (int nIndex)
        {
            if (nIndex == m_nvFather[nIndex])
            {
                return nIndex;
            }
            return  m_nvFather[nIndex] = __find (m_nvFather[nIndex]);
        }
    
    private:
        vector<int>                m_nvFather ;    // 父亲数组
        vector<int>::size_type m_nSetEleCount ;    // 集合中结点个数
    } ;
    
    class MST_Kruskal
    {
        typedef priority_queue<TreeNode> MinHeap ;
    public:
        MST_Kruskal (const vector<vector<int> >& graph) 
        {
            m_nNodeCount = static_cast<int>(graph.size ()) ;
            __getMinHeap (graph) ;
        }
        void DoKruskal ()
        {
            UnionSet us (m_nNodeCount) ;
            int k = 0 ; 
            while (m_minheap.size() != 0 && k < m_nNodeCount - 1) 
            {
                TreeNode tn = m_minheap.top () ;
                m_minheap.pop () ;
                // 判断合理性
                if (us.Union (tn.m_nVertexIndexA, tn.m_nVertexIndexB)) 
                {
                    m_tnMSTree.push_back (tn) ;
                    ++ k ;
                }
            }
            // 输出结果
            for (size_t i = 0; i < m_tnMSTree.size() ; ++ i) 
            {
                cout << m_tnMSTree[i].m_nVertexIndexA << "->"
                    << m_tnMSTree[i].m_nVertexIndexB << " : "
                    << m_tnMSTree[i].m_nWeight 
                    << endl ;
            }
        }
    
    private:
        void __getMinHeap (const vector<vector<int> >& graph) 
        {
            for (int i = 0; i < m_nNodeCount; ++ i) 
            {
                for (int j = 0; j < m_nNodeCount; ++ j) 
                {
                    if (graph[i][j] != numeric_limits<int>::max()) 
                    {
                        m_minheap.push (TreeNode(i, j, graph[i][j])) ;
                    }
                }
            }
        }
    private:
        vector<TreeNode>    m_tnMSTree ;
        int                    m_nNodeCount ;
        MinHeap                m_minheap ;
    } ;
    
    
    int main ()
    {
        const int cnNodeCount = 6 ;
        vector<vector<int> > graph (cnNodeCount) ;
        for (size_t i = 0; i < graph.size() ; ++ i) 
        {
            graph[i].resize (cnNodeCount, numeric_limits<int>::max()) ;
        }
        graph[0][1]= 6 ;
        graph[0][2] = 1 ;
        graph[0][3] = 3 ;
        graph[1][2] = 5 ;
        graph[1][4] = 3 ;
        graph[2][3] = 5 ;
        graph[2][4] = 6 ;
        graph[2][5] = 4 ;
        graph[3][5] = 2 ;
        graph[4][5] = 6 ;
    
        graph[1][0]= 6 ;
        graph[2][0] = 1 ;
        graph[3][0] = 3 ;
        graph[2][1] = 5 ;
        graph[4][1] = 3 ;
        graph[3][2] = 5 ;
        graph[4][2] = 6 ;
        graph[5][2] = 4 ;
        graph[5][3] = 2 ;
        graph[5][4] = 6 ;
    
        MST_Kruskal mst (graph);
        mst.DoKruskal () ;
    }

    参考资料

    1. Donald E.Knuth 著,苏运霖 译,《计算机程序设计艺术,第1卷基本算法》,国防工业出版社,2002年
    2. Donald E.Knuth 著,苏运霖 译,《计算机程序设计艺术,第2卷半数值算法》,国防工业出版社,2002年
    3. Donald E.Knuth 著,苏运霖 译,《计算机程序设计艺术,第3卷排序与查找》,国防工业出版社,2002年
    4. Thomas H. Cormen, Charles E.Leiserson, etc., Introduction to Algorithms(3rd edition), McGraw-Hill Book Company,2009
    5. Jon Kleinberg, Ėva Tardos, Algorithm Design, Addison Wesley, 2005.
    6. Sartaj Sahni ,《数据结构算法与应用:C++语言描述》 ,汪诗林等译,机械工业出版社,2000.
    7. 屈婉玲,刘田,张立昂,王捍贫,算法设计与分析,清华大学出版社,2011年版,2013年重印.
    8. 张铭,赵海燕,王腾蛟,《数据结构与算法实验教程》,高等教育出版社,2011年 1月
    展开全文
  • 贪心贪心法 补充内容 算法
  • 贪心导论

    千次阅读 2018-05-12 21:49:00
    一、什么是贪心在算法与思想不断多样化的 OI 世界里,有一样东西。它既是一种思想,一种普及大众、简单快捷的思想;又是一种算法,一种几乎无所不能、高效率、经济实用的算法。它是 OI 新手们忠实崇拜的偶像,又是 ...

    一、什么是贪心

    在算法与思想不断多样化的 OI 世界里,有一样东西。它既是一种思想,一种普及大众、简单快捷的思想;又是一种算法,一种几乎无所不能、高效率、经济实用的算法。它是 OI 新手们忠实崇拜的偶像,又是 OI 大牛们理想的最高境界。没错,这个东西,就是————贪心。常言道:“贪得无厌。”然而,面临多元化的 OI,我们不得不选择贪心。为什么?因为贪心是紧随时代潮流的。曾经有一位 OI 贪心大牛说过,“给我一道题,我就能贪心”,这就是最高境界。有人会问:“贪心究竟是什么?”我无法准确回答,因为没有标准答案。在每个人心目中,贪心的定义是不同的。思想不同,算法也不同;但有一个共同目的————将思想简单化。曾经有位大牛写过一篇《骗分导论》,我很喜欢。在我看来,贪心就是一种高水平的骗分技术。“有技术,一等奖也贪得来”,这就是我的信仰。还有人说:“贪心很困难。”正因如此,今天,我写下这篇《贪心导论》,以此与各位 OIer 们共享经验教训,也当作是考前的娱乐消遣。

    Tips:本文适合 OI 新手 和 尚未成为大牛的 OIer 们阅读。对于大牛级别,非本人所能言语;且文中部分内容有一点****的嫌疑,故大牛们姑且观之,仅作娱乐。 一起奔向 NOIP! 

    二、贪心的实际应用

    今天,OI 崇尚的是 动态规划、搜索 相结合。然而,我却要在这里说贪心,原因何在?在于 贪心的广泛性 。首先不得不说明的是,本人的贪心技术还不够到位,因此,本人对贪心的定义就是: 尽可能地多拿分 ,而非以 AC 为目标。

    举几个简单例子来说明一下。

    [例 1]有 N 个人排队接水。

    每个人接水所用的时间不同,而一个时刻只能有一个人接水,且只有等一个人接完水后,另一个人才能开始接水。现在请你求出 N 个人接水的顺序,使得每个人所用平均时间最短,并输出这个最短平均时间。这道题是贪心的经典例题了。当初此题发布时,有人想当然地认为是动态规划去求解。虽然此题用动规也能解决,但是有没有更简单的方法呢?——当然有,就是贪心。联系一下生活实际:排队的时候,如果出现拥挤情况,怎样做才能节约时间呢?让耗费时间最短的人先来,还是让耗费时间最长的人排第一?这样一想,问题就变得简单了,贪心策略也出来了————让耗费时间短的人排在前面。于是一个快排,轻松解决。看看这效率,那叫一个高啊~~~~~~~~~~~

    [例 2]经典背包问题。

    一个体积为 V 的包,现在有 N 个物品,每个物品都有一个体积和一个价值。现在让你求出一个最佳方法,使得放进背包里的物品的价值尽可能大(当然放进去的物品总体积不会大于背包体积)。这个问题我想就不用我废话了吧?也是经典的贪心问题,一种较优的策略为:将性价比高的物品尽可能多地往里放。虽然由于数据不会太弱而难以 AC,但分肯定是多拿定了。而且,通过贪心,有效节约了时间,用以分配到其他难题上,可谓两全其美。(当然,此题用动规一样简单高效,本人只是稍稍强调一下贪心的效率而已,绝无他意~~~)从以上例子中可以看出贪心在 OI 实际中的广泛应用了。总之一句话:贪心才是王道!掌握贪心,与掌握动规同样重要!

    三、常用贪心方法(策略)

     接下来就是本人的自主品牌了~~~~~经过长时间的摸爬滚打,本人研究出一套常用贪心方法(策略),
    个人感觉很实用。本人曾凭借它成功拿下过 773 分。
    值得一提的是,贪心在大多数情况下只是一种思想,因此需要一种算法作为媒介才能得以实现。而
    我所做的,不过是帮其匹配而已。

    No.1 裸搜 + 贪心 = 裸贪

    不要误会,名字纯属娱乐。说得直接点,就是贪心的思想,用深搜(不加剪枝的深搜称作“裸搜”)来实现。不要被吓到了。这是最基础也最常用的贪心策略,关键时刻用它足以左右命运。
    [例 1]著名的“炒股票”问题。现在你手里有 1000 元,在接下来的 N 天中,你可以选择将手中的现金按当天价格购买股票,也可以将手中的股票兑换成现金。已知第 i 天的股票价格为 a[i](单位:元/股)。现求出第 N 天时手里能拥有的最多现金数量。1<=N<=15。
    这道题很简单,就是一个简单动规。不过如果有的人用动规做不出来的话(只是“如果”而已,我并不是贬低各位水平~~~),就得考虑——贪心。
    首先很容易想到:每天 要么全部买进或卖出,要么什么都不做 。因为每天要么会赚(要赚就要多赚点,于是全买或卖),要么不会赔(什么都不做就不会赔了)。有了这一点,其实动规已经很容易了。不过呢~~~我就是要贪!怎么办?注意题目的数据范围。考虑到 N 的值很小,在深搜可以承受的范围内,于是我们可以用 裸贪来解决这道题了。策略就是:搜索每一天的两种决策,不断替换最优。一样 AC。
    程序实现也很容易。
    [贪心程序伪代码]
    procedure dfs(m:byte);
    begin
     if 到达边界 then 替换最优并退出;
     否则 全买成股票 or 全卖成现金 or 什么都不做;
     dfs(m+1);//在当前情况下搜索下一天的决策
     撤销修改;
    end;
     

    [例 2]现在有 N 件工作。每件工作可能会依赖于其他工作(该工作必须等其所依赖的工作全部结束后才能开始,一个工作最多依赖于 10 件工作)。假设 1 个时刻只能完成一个工作,现在求出第 M 件工作最早完成的时间。数据保证没有循环依赖。

    初看题,是一个多叉树结构。有的同学一看跟树有关就甩掉不做了(俗称“树型恐惧症”)。其实仔细一考虑:没有环,数据也不是太大……那么,从目标点出发搜索所有依赖对象直到目标点的依赖对象全部完成为止,就是一个简单的裸贪问题了,根本用不着什么树。(当然你要用树我也没办法~~~)

     [贪心程序伪代码]
    procedure dfs(i:integer);
     begin
     if 目标的依赖对象已经全部完成 then 输出结果并退出;(注意:首先搜索出的结果一定是最优!)
     否则 标记当前结点并搜索点 i 的所有依赖对象;

     end;


     由上能够看出裸贪的高效率。其实,对于一些复杂的动态规划和广搜题目,用裸贪都能取得一定的成效(虽然不一定能 AC,比如上面例子中 N=1000~~~~)。对于考试中的应急措施, 裸贪 可谓首选。

    No.2 枚举 + 贪心 = 枚贪

    仿照上面来理解的话就是用枚举的方法来实现贪心。这个实现起来就更容易了。枚举嘛,N 重循环都能搞的定的东西。可惜的是,效率不太高,想要 AC 不容易。
    [例 1]小 S 一天一餐只吃 N 顿饭。每顿饭会有 M 份食物供其选择。这些食物又被分成 K 类。根据小M 的爸爸规定,小 M 每顿饭吃第 i 类食物的数量不能超过 a[i]。每份食物都有一个营养值。问小 M 应该怎样安排饮食,使得每顿饭可以获得更多营养值。有的 OIer 们一看此题,条件反射般地联想到背包问题,于是不亦乐乎地动态规划 ing~~~~停!既然背包问题可以贪心,这个题为什么就不能呢?其实就是一种最低级的贪心策略:每次找能够吃的食物中营养值最大的一份。还是一个快排,挨个枚举,搞定!很简单吧?不过有的大牛们反而会被这种简单题给迷惑,把思想复杂化了。所以,简单就好。(代码略。太简单了用不着我说了吧?)
    [例 2]现在有 N 个数,要求前 M 个数的乘积刚好等于后 N-M 个数的乘积,求这样的数序列有多少个。1<=N<=8。这是一道典型的优化深搜题。但是在考场上,有的同学们只能想到深搜,而想不到优化(即 裸搜 )。而裸搜是肯定要超时(或者爆掉)的。怎么办?用 枚贪或许可以帮助解决此题。
    仔细思考一下:既然搜 8 个数会挂,那么搜 4 个行不行呢?如果行,剩下 4 个又怎么办呢?因此,我们想到:只搜索前 M 个数,枚举后 N-M 个数;且当后 N-M 个数之积已经大于前 N 个数之积时果断退出。这样一来,时间复杂度虽然没有太大优化,但空间复杂度大大降低了(搜索深度降低了)。当时的我因为 RP 爆发,用 枚贪 一次 AC,实乃幸运(其中有一组是卡着 1s 的时间过的~~~~)。
    [贪心程序伪代码]
    procedure dfs(I:byte);;
    begin
     if 后 N-M 个数的积大于前 N 个数 then 退出;
     If 满足条件 then 记录结果并退出;
     If (i=m) and 没有满足条件 then 退出;
     Dfs(I+1);
    End;
    begin
     枚举后 N-M 个数;
     dfs(1);;
    end.

    在实际操作中,枚贪 容易实现但多半不能 AC,过 5、6 组就是运气了。

    No.3 模拟 + 贪心 = 模贪

    用 模拟 来贪心,是一种稍高级的方法。

    [例]著名的俄罗斯方块游戏大家都玩过吧?现在有一种简单的方块游戏:有宽度为 W 的屏幕,有 N个边长不一的正方形方块先后从上往下掉,且每一步在保证最大高度尽可能小的情况下尽可能地向左放。现给出每个方块的边长,请你求出方块掉落完后的最大高度(假设屏幕高度无限)的最小值。又是一道蛊惑人心的题。题目最后的“最小值”一词是一个陷阱,让人瞬间误认为是求最优解问题,从而考虑动规。其实按照题目描述理解的话,此题的答案相对于数据来说是惟一的,贪心策略也显而易见了:每步累加每个宽度对应高度的最大高度,从中找最小的掉落下来。简单的模拟就能搞定。

    [贪心程序源代码]

    var
     i,j,k,n,w,max,min,min1:longint;
     high,high1:array[0..20] of longint;
     a:array [0..100] of longint;
    begin
     readln(n,w);
     for i:=1 to n do readln(a[i]);
     fillchar(high,sizeof(high),0);
     for i:=1 to n do
     begin
     fillchar(high1,sizeof(high1),0);
     for j:=1 to w-a[i]+1 do
     for k:=j to j+a[i]-1 do
     begin
     if high1[j]<high[k] then high1[j]:=high[k];
     end;
     min:=high1[1];
     min1:=1;
     for j:=2 to w-a[i]+1 do
     if high1[j]<min then
     begin
     min:=high1[j];
     min1:=j;
     end;
     for k:=min1 to min1+a[i]-1 do
     begin
     high[k]:=min+a[i];
     end;
     end;
     max:=0;
     for i:=1 to w do if max<high[i] then max:=high[i];
     writeln(max);
    end.
    因为用 模拟 的方法来贪心的时候并不多,因此就不多讲了。大家有兴趣可以亲身体会一下。

    No.4 动规 + 贪心 = 动贪

     本年度最高级也最深奥的贪心方法!动规本身就难,还要用动规来贪心,更是难上加难!我向来最讨厌动规,但对于 动贪 还是不得不罗嗦几句。没办法,老大啊!
     [例]现在你安排 N 个人吹 M 个气球。已知第 i 个人每分钟可以吹 a[i]个气球,吹一分钟后要休息 b[i]分钟。现在求吹完 M 个气球所用的最短时间。当然,每分钟只能有一个人吹气球。(1<=b[i]<=4) 当初做这道题时,想到低级的 枚贪(每次找能吹的人中吹的最多的一个) ,但是只过了 9 组。万般无奈之下参看标程(当然是纯动规了,6 维的),发现标程果然很经典!因为休息时间最多也才 4 分钟,因此我们想到一个超高级的贪心策略:枚举后 4 分钟吹气球的人,借以递推求解。这样一来就完全没有了反例,也不会超时,虽然麻烦了点,但是绝对的 AC!(因为是动规,虽然代码不长,但是也不想写了
    ~~~~~)
    动贪 的效率是其他贪心方法所远不能及的,也是几乎可以保证 AC 的贪心方法。 编程复杂度 是它的惟一缺陷,因为很有可能在考场上你多半想不出要 动贪 ,即使想出了,冗长的代码也会令你望而却步。正因如此, 动贪 才成为了大牛们的终极目标之一。对于菜菜的本人来说,就算了吧~~~~掌握好以上三种贪心就行了。

    No.5 树论 + 图论 + 贪心 = 树图双贪

     这是一种较少见的贪心方法,因为遇到图论首先想到的是 Krim、Floyed、SPFA 等高级算法,而不会首选贪心;只有在无可奈何的情况下,才会选择 树图双贪 来凑合凑合。虽然是下策,但是不到最后,还不会知道会发生什么呢~~~~~~~~~~~~~~~

    [例]二叉树有很多种,但是它们很多都是等价的。某二叉树通过把某非根结点作为根结点而保持其它各结点之间的关系不变,重新建立出一棵树,若这棵树是一棵二叉树,则称这两棵二叉树等价。现在给出一棵基准二叉树,请你判断给出的其他树是否和它等价。(图略,因为对于贪心来说不重要~~~)题目叙述相当复杂,即使有示意图,部分 OIer 们也是一头雾水,于是毅然放弃。不过没关系,即使不懂题意,仍然可以贪心,因为 贪心无极限 嘛!此题应该如何贪心呢?

    首先想到一个树的常用术语——度。既然只是判断是否等价,那么,统计所有结点的度并比较可不可以呢?肯定是有一定根据的。这是最简单的贪心策略,效率达到了 通过 9 组 之高!这是树型贪心。再考虑图的常用算法:本题的二叉树变形只是基于各结点间的相互位置,因此我们想到:利用 Floyed算法求出两点间的最短距离再加以判断。这就是 图论贪心 了。虽然不太好理解,但是它的效率说明了一切:AC!我们不得不服气了。贪心就是如此,搞得你很郁闷却又不得不接受现实。关于 树图双贪 ,就点到为止。如果哪位大牛有意愿与本人交流一下此方面的问题(因为我是不擅长树论和图论的,所以自然不会用此方法~~~~),请发言。本人倒是兴致勃勃呢~~~ 

    No.6 乱搞 + 贪心 = 乱贪 ?

    最低级的骗分伎俩,纯属贪图速度,因此效率极低~~~~~当然,乱搞无语,贪心有理,我们还是要见识一下 乱贪 在关键时刻的威力。
    [例](某次模拟赛的一道题)现在老师交给小 X 一个光荣而艰巨的任务:在规定的 T 时刻前完成若干项任务。给出每项任务的最迟完成时间和完成所需时间,请你判断小 X 能否顺利完成任务。因为老师很 BT,而且小 X 的 RP 极低,因此任务的数量可能会超过 Maxlongint。一个时刻只能做一件任务,并且要做就要做到底。若能完成,输出“Winner”;否则,输出“Beaten”。
    此题的数据相当之 BT(高精度是肯定的),繁杂的数据处理几乎令每一个 OIer 崩溃。此时,无论用前面所讲的什么贪心方法,似乎对此题的复杂度都起不到太大作用。那么,现在的我们,是否就一筹莫展了呢?——————————还没有结束。事已至此,就别怪我更 BT 了————乱贪!
    由于乱贪的方法太多(想得到的都算),这里只介绍两种比较 BT 的:
    1. If 任务数<=T then writeln(‘Winner’) else writeln(‘Beaten’) .可以得 20 分;
    2.Writeln(‘Beaten’)。我当时是这么想的:此次模拟赛应该有一定的恶搞成分,题目中的小 X 应该是出题人的某位好友;既然如此,借此机会,何不捉弄他一番?反正只是娱乐而已。于是,数据中结果为 Beaten 的~~~~~~~~~~~~~~~~~~~~竟有 8 组!于是 80 分到手了。下来一看标程,洋洋洒洒写了 90多行。(什么题啊这是~~~~~)
    出现这种状况,只能怪 RPWT 了。毕竟人心变幻莫测,在结果之前你永远不知道接下来会发生什么。因此, 乱贪 仅限于保命用,平时尽量不用。(详情请参考《RP 导论》以提高 RP)

    四、贪心技巧

    说了这么多,本人要强调的只是 贪心思想的有效运用 ;也许你会认为我上面所讲的并不是以 贪心 为重点——————本来就不是。贪心只是桥梁而已,真正发挥关键作用的还是日常积累的算法。所以,不要被贪心所引诱从而放松日常算法的学习加深,否则后果很严重(猜猜看,谁是受害者?)。
    有的人认为贪心很难,难在思想。算法是无穷的,题目是多样的,要在数不清的题目面前,找出数不清的贪心策略,从中选择最优,并从数不清的算法中,搭配最合适的一种······想想都很恐怖了。为此,在 NOIP2017 的前夕,本人仅持个人观点,向各位小牛(大牛就不用听了~~~)们提出以下建议:
    ⒈遇题先不要忙着贪心。一些数学问题是贪心所不能及的;一些送分题又无须贪心就能解决的。先中规中矩地处理掉简单题,再考虑从 贪心 下手。
    ⒉先枚举,后模拟,实在不行用搜滴~~~~也就是说,实在不行要贪心的话, 枚贪 是首选(方便哪!);如果数据的规模超出了枚举的极限,就考虑 模贪 (稳扎稳打,不费劲);如果数据的复杂度相当高,以至于超出模拟的承受规模,就只有忍气吞声,用 裸贪 (最好加点优化。反正我没有那个习惯~~)以求得分了。通常情况下,一次成功的 枚贪 可以拿到 50 或 60 分,一次成功的 模贪 也差不多70 分左右;当数据规模较小时, 裸贪 有 AC 的可能,一旦规模 BT 起来~~~~~30 分就足够了。——————至于 动贪 等高等贪心,有本事的人当然就用,没本事的就老实点吧~~~~最后重申,不推荐 乱贪 !

    ⒊越是贪心,越要细心。虽然贪心能够降低编程复杂度,但是我们决不能掉以轻心。最简单的程序都实现不了,高难度的又怎么办?本人最初学习贪心时,每一次几乎都能找到合适的策略,但总是一败涂地。原因就在于 全局变量与局部变量混淆、函数与过程的混淆、变量太多引起混淆 等一系列基础错误。平时,可能会有一天的时间来调试一道题目;上了考场,连 贪心 都要调试两个小时,那你还能做什么?

    贪心也讲究扎实的基本功。

    ⒋注重思维锻炼,提高思维的活跃性。贪心是一门艺术,也是对大脑思维的考验。通常情况下,思维越活跃,视野越开阔,联想越丰富,从而对贪心起到了极大的促进作用。所以有调查显示,越是捣蛋分子,越能贪!(举个思维活跃的例子:我的钱包哪儿去了?找一下:先枚举几乎所有可能的地方,如果是白费劲,然后静下心来模拟一下“案发现场”;如果记忆力衰竭的话就来个大搜索,一个死角也不放过!)
    ⒌加强记忆化的能力。众所周知,无论是动态规划还是搜索,记忆化思想是很必要的。贪心同样需要记忆化,因为一种贪心方法如果能够对付一道题,那么对于相类似的题,也应该行的通。记忆化,已一起奔向 NOIP! 贪心导论 By envelope2

    经成为大众化的需求
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 215,328
精华内容 86,131
关键字:

对你贪心