GreedyAlgorithms20161226

Index
1．	贪心法的基本思想
2．	贪心法的设计要素
3．	应用：单源最短路径、最优装载问题、分数背包问题（算法）、活动安排（算法、正确性证明）——所有算法时间复杂度
Content
（一）理解贪心算法的基本思想
  贪心算法是一种在当前状态下每一步都选择最优的选择（所以很贪心）， 希望从局部的最优解得到整体的最优解，贪心算法对于大部分的优化问题都能产生最优解，但不能总获得整体最优解，通常可以获得近似最优解。
  贪心算法需要符合两个基本要素：
    un.贪心选择性质：贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择， 当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果，（因此我们说它目光短浅）
    deux.最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
（二）设计要素
    un.贪心算法适合于组合优化问题
    deux.求解过程是多步判断的过程，最终的判断序列对应于问题的最优解。
    trois.判断某种“短视的”（就是只看眼前）贪心选择性质判断，性质好坏决定算法的成败
    quatre.贪心算法必须进行正确性证明
    cinq.证明贪心算法不正确的技巧，举反例。
 （三）应用
    un.单源最短路径
    
        给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
     
  Dijkstra算法是解单源最短路径问题的贪心算法。
用带权的有向图表示一个交通运输网，图中：
顶点——表示城市
边——表示城市间的交通联系
权——表示此线路的长度或沿此线路运输所花的时间或费用等
问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径

    deux.最优装载问题
    
        [问题描述]有一批集装箱要装上一艘承重量为C的轮船。其中集装箱i的重量为Wi.最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱撞上轮船。
        [策略]采用重量最轻者先装的贪心选择策略 
         void Loading(int x[], Type w[], Type c, int n)
        {
           int *t = new int [n+1];
           Sort(w, t, n);
           for (int i = 1; i <= n; i++) x[i] = 0;
           for (int i = 1; i <= n && w[t[i]] <= c; i++) 
           {x[t[i]] = 1; c -= w[t[i]];}
        }

    
    trois.分数背包问题（算法）
    
    1、背包问题：
        给定n个重量为(w1,w2,…,wn),价值为(v1,v2,…vn)的物品和一个容量为C的背包,要求选择部分物品装进背包,使得背包内物品价值总和最大.
        1) 问题的解   (x1,x2,…xn)     0 ≤ xi ≤ 1
        2)  约束条件   ∑xi wi ≤ C
        3)  目标函数   ∑xi vi    达到最大
    解题思路:
        1) 尽可能多选择价值大的物品.
        2) 尽可能多选择重量轻的物品.
        3) 尽可能多选择价值/重量比大的物品.
        贪心法的一般过程
        1) 根据题意选取一种度量标准或贪心策略.
        2) 按度量标准对n个输入排序.
        3) 按序做出贪心选择.
        4) 检查该选择是否与前面的选择构成可行解.
        5) 如果可行,则将该选择加入解中, 否则不加入.
        6) 继续做下一步选择.
    Greedy-knapsack( )
      { 将物品按v/w从大到小排序
         for (i=1; i<=n; i++) x[i]=0;
         for (i=1; i<=n; i++)
             if (w[i]<c)
                 { x[i]=1; c=c-w[i] }         
              else { x[i]=cu/w[i]; break; }
         output x[1]…x[n]
       }
    quatre.活动安排（算法、正确性证明）
    
    
    
    
    
    cinq.所有算法时间复杂度