算法簡介

貪心算法是指：在每一步求解的步驟中，它要求“貪心”的選擇最佳操作株汉，并希望通過一系列的最優(yōu)選擇橘荠，能夠產(chǎn)生一個問題的（全局的）最優(yōu)解。
　　貪心算法每一步必須滿足以下條件：
　　1郎逃、可行的：即它必須滿足問題的約束哥童。
　　2、局部最優(yōu)：他是當前步驟中所有可行選擇中最佳的局部選擇褒翰。
　　3贮懈、不可取消：即選擇一旦做出，在算法的后面步驟就不可改變了优训。

基本思路

1.建立數(shù)學模型來描述問題
2.把求解的問題分成若干個子問題
3.對每一子問題求解朵你，得到子問題的局部最優(yōu)解
4.把子問題對應的局部最優(yōu)解合成原來整個問題的一個近似最優(yōu)解

實際案例

案例一

假設有如下課程，希望盡可能多的將課程安排在一間教室里：

1.選擇結(jié)束最早的課揣非，便是要在這教室上課的第一節(jié)課
2.接下來抡医，選擇第一堂課結(jié)束后才開始的課，并且結(jié)束最早的課早敬，這將是第二節(jié)在教室上的課忌傻。
這邊的選擇策略便是結(jié)束最早且和上一節(jié)課不沖突的課進行排序，因為每次都選擇結(jié)束最早的搞监，所以留給后面的時間也就越多水孩，自然就能排下越多的課了。每一節(jié)課的選擇都是策略內(nèi)的局部最優(yōu)解(留給后面的時間最多)琐驴，所以最終的結(jié)果也是近似最優(yōu)解(這個案例上就是最優(yōu)解)俘种。

案例二（哈夫曼編碼）

??哈夫曼編碼指的是由哈夫曼提出的一種編碼方式秤标，他完全依據(jù)字符出現(xiàn)的頻率來構(gòu)造一種平均長度最短的編碼。也稱作最佳編碼宙刘。而這種編碼方式苍姜，也屬于貪心算法的一項比較典型的應用，他主要應用于文件壓縮領(lǐng)域悬包。
??我們知道ASCII 一共有128個字符衙猪，因此，如果要保存這些字符玉罐，最少要占用log128個bit屈嗤。同理，如果字符個數(shù)為C吊输，至少要占用logC個Bit饶号。舉個簡單的例子：假如有一個文件，只包含一些字符：a,e,i,s,t季蚂，并且加上一些空格和newline(換行)茫船，一共7種字符，所以每個字符最少占用log7個bit扭屁，也就是3個bit算谈，如圖所示，假如一共有58個字符料滥，因此所有字符加起來最少需要占用3*58=174個比特空間然眼。

如果要對這些數(shù)據(jù)進行壓縮，有什么簡單的辦法嗎葵腹？答案就是哈夫曼編碼高每。他能夠使得一些普通的文件普遍節(jié)省25%的空間，甚至能夠使得一些大型文件節(jié)省百分之五十到七十的空間践宴。而他的策略就是更具字符出現(xiàn)的頻率鲸匿，讓每個字符占用大小不一的空間。需要注意的一點就是阻肩，如果所有字符出現(xiàn)的頻率是一樣的話带欢，那么對于占用空間的壓縮是不存在的。
??如下圖所示烤惊，我們可以通過二叉樹來表示字母的二進制乔煞。
數(shù)據(jù)結(jié)構(gòu)如下圖所示：

WX20190312-174253@2x.png

該二叉樹需要具有如下特點：

• 節(jié)點要么是葉子結(jié)點，要么必須有兩個子節(jié)點
• 字符數(shù)據(jù)都是放在葉子結(jié)點上面
• 從根節(jié)點開始撕氧，用0表示左分支瘤缩，1表示右分支，因此所有的字符編碼可以表示為如下：a: 000 ; e: 001; i: 010; s: 011; t: 100 ; sp:101; nl: 11
• 任何字符都不是其他字符的前綴伦泥，這種編碼也叫前綴碼剥啤，否則的話翻譯成字符的話就不能確保唯一性，例如編碼：0100111100010110001000111可以很容易的翻譯成(i s newline a sp t i e newline)不脯， 因為0不可能是字符府怯，01，也不是字符防楷，010是字符牺丙，0100不是字符，所以第一個字符只能是i复局，后面的同理可得冲簿。

通過上圖所示的二叉樹，可以看出nl從之前的占用3個bit亿昏，減少為占用了2個bit峦剔，因此，可以計算出他的占用空間減少為171個bit角钩，初步看來并沒有節(jié)省太大的空間吝沫，這是因為上圖中的二叉樹并不是最優(yōu)前綴碼。如下圖所示递礼，如果改為最優(yōu)前綴碼之后惨险，效果如圖所示，一共節(jié)省了174-146=28個字符脊髓。

WX20190312-175756@2x.png

??怎么生成最優(yōu)前綴碼辫愉，其實用的就是哈夫曼算法，我們可以把每個字符出現(xiàn)的頻率當作他的權(quán)值将硝，權(quán)值越大恭朗，出現(xiàn)的頻率越高。他可以描述為：首先通過權(quán)值最低的兩個結(jié)點生成一個新的父節(jié)點袋哼，新的父節(jié)點的權(quán)值等于他的子節(jié)點的權(quán)值之和冀墨，并命名為T1，之后再在剩余的節(jié)點和T1中查找出權(quán)值最低的兩個節(jié)點涛贯，生成新的父節(jié)點诽嘉，直到所有節(jié)點都生成一棵新的二叉樹，則這顆新的二叉樹就是最優(yōu)二叉樹弟翘，也叫最優(yōu)前綴碼虫腋。以上面的字符數(shù)據(jù)為例：

初始狀態(tài)：

截圖.png

第一步：
由于s和nl出現(xiàn)的頻率最低，通過s和nl生成新的二叉樹節(jié)點稀余，新的節(jié)點權(quán)值=s(權(quán)值)+nl(權(quán)值) = 4

截圖1.png

第二步：
由于T1和t現(xiàn)在權(quán)值最低悦冀，因此，T1和t生成新的二叉樹節(jié)點T2睛琳，T2的權(quán)值為8盒蟆。

截圖2.png

第三步：由于T2和a現(xiàn)在為權(quán)值最低的兩個節(jié)點踏烙，把他生成新的二叉樹節(jié)點T3,T3的權(quán)值為18.

截圖.png

第四步：剩下的i和sp為權(quán)值最低的兩個點了，把i和sp生成新的二叉樹節(jié)點T4,T4的權(quán)值為25.

截圖.png

第五步：e和T3生成新的節(jié)點T5,T5的權(quán)值為33.

截圖.png

第六步：只剩下T4和T5兩個節(jié)點了历等，把T4,T5生成新的節(jié)點T6讨惩，他的權(quán)值為58，第六步后寒屯，也是最后一步生成的二叉樹也是最終的二叉樹荐捻，他也被稱為最優(yōu)二叉樹。

截圖.png

具體代碼實現(xiàn)

定義節(jié)點的數(shù)據(jù)結(jié)構(gòu)Node.class

public class Node implements Comparable<Node>{
    private int primary; //節(jié)點的權(quán)值
    private Node leftNode; //節(jié)點的左子節(jié)點
    private Node rightNode; //節(jié)點的右子節(jié)點
    private char value; //節(jié)點代表的字符

    public Node(int primary){
        this.primary = primary;
    }

    public void setValue(char value) {
        this.value = value;
    }

    public int getPrimary() {
        return primary;
    }

    public char getValue() {
        return value;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public int compareTo(@NonNull Node o) {
        return primary - o.primary;
    }
}

定義全局變量：

 char[] chars = {'a','e','i','s','t',' ','\n'};//字符數(shù)組
 int[] fraq = {10,15,12,3,4,13,1}; //字符對于出現(xiàn)頻率
 Map<String,String> enCodeMap = new HashMap<>(); //保存不同字符對應的路徑
 LinkedList<Node> list = new LinkedList<>(); //保存初始化的節(jié)點列表

初始化數(shù)據(jù)結(jié)構(gòu)：

//初始化數(shù)組列表并排序
for(int i = 0;i<chars.length;i++){
        Node node = new Node(fraq[i]);
        node.setValue(chars[i]);
        list.add(node);
}
Collections.sort(list);

構(gòu)建二叉樹

  private void buildTree(){
        while(list.size() > 1){
            //取出出現(xiàn)頻率最低的兩個節(jié)點
            Node node1 = list.get(0);
            Node node2 = list.get(1);
            //生成新節(jié)點
            Node newNode = new Node(node1.getPrimary()+node2.getPrimary());
            //設置新節(jié)點左右子樹
            newNode.setLeftNode(node1);
            newNode.setRightNode(node2);
            //從數(shù)組中移除頻率最低的兩個節(jié)點
            list.remove(0);
            list.remove(0);
            //新的節(jié)點按照出現(xiàn)頻率從低到高的原則插入列表
            addNewNodeToList(newNode);
        }
    }

新節(jié)點插入

private void addNewNodeToList(Node newNode){
        int index;
        for(index = 0; index < list.size();index++){
            //按照權(quán)值從小到大的順序插入列表
            if(newNode.getPrimary() <= list.get(index).getPrimary()){
                list.add(index,newNode);
                break;
            }
        }
        if(index == list.size()){
            list.addLast(newNode);
        }
    }

獲取最優(yōu)二叉樹的路徑

private void encoding(Node node,String encoding){
        if (node!=null){
            if (node.getLeftNode()==null && node.getRightNode()==null){
                enCodeMap.put(node.getValue()+"",encoding);
            }
            encoding(node.getLeftNode(),encoding+"0");
            encoding(node.getRightNode(),encoding+"1");
        }
}

打印最終結(jié)果

private void printTreeNode(){
        //打印生成的字符編碼
        for(String str:enCodeMap.keySet()){
            if(str.charAt(0) == ' '){
                System.out.print("sp:");
            }else if(str.charAt(0) == '\n'){
                System.out.print("nl:");
            }else{
                System.out.print(str+":");
            }
            System.out.print(enCodeMap.get(str));
            System.out.print("\n");
        }
    }

打印結(jié)果:

sp:01
a:111
s:11001
t:1101
e:10
i:00
nl:11000

重新計算占用空間：

案例三（紙幣找零問題）

??假如有1元寡夹、2元处面、5元、10元的紙幣菩掏，如果要找16塊錢零錢魂角，正常只需要1張10元+1張5元+1張1元紙幣 = 16，而這肯定也是最優(yōu)的解決方案患蹂。他的策略是要湊夠目標數(shù)字,用文字描述如下就是或颊，永遠先找最大的紙幣，判斷是否超過目標值传于，超過則換下一張最大的紙幣囱挑，知道湊夠的紙幣值等于目標值。而這種策略也被叫貪心算法沼溜。
??但是這種策略不一定每次都保證有效平挑，比如對于1、5系草、7元紙幣通熄，比如說要湊出10元，如果優(yōu)先使用7元紙幣找都，則張數(shù)是4張唇辨，（1+1+1+7），而真正的最優(yōu)解是5+5=10能耻，2張赏枚。

總結(jié)

• 貪心算法試圖通過局部最優(yōu)解找到整體最優(yōu)解
• 最終得到的可能是最終最優(yōu)解，但也有可能是近似最優(yōu)解
• 貪心算法大部分情況下易于實現(xiàn)晓猛，并且效率不錯

文章引用：

http://www.reibang.com/p/b613ae9d77ff
http://www.reibang.com/p/fede80bad3f1
https://www.cnblogs.com/kubixuesheng/p/4397798.html