贪心算法 - 简书

算法简介

贪心算法是指：在每一步求解的步骤中，它要求“贪心”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。
　　贪心算法每一步必须满足以下条件：
　　1、可行的：即它必须满足问题的约束。
　　2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
　　3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。

基本思路

1.建立数学模型来描述问题
2.把求解的问题分成若干个子问题
3.对每一子问题求解，得到子问题的局部最优解
4.把子问题对应的局部最优解合成原来整个问题的一个近似最优解

实际案例

案例一

假设有如下课程，希望尽可能多的将课程安排在一间教室里：

课程	开始时间	结束时间
美术	9AM	10AM
英语	9:30AM	10:30AM
数学	10AM	11AM
计算机	10:30AM	11:30AM
音乐	11AM	12PM

1.选择结束最早的课，便是要在这教室上课的第一节课
2.接下来，选择第一堂课结束后才开始的课，并且结束最早的课，这将是第二节在教室上的课。
这边的选择策略便是结束最早且和上一节课不冲突的课进行排序，因为每次都选择结束最早的，所以留给后面的时间也就越多，自然就能排下越多的课了。每一节课的选择都是策略内的局部最优解(留给后面的时间最多)，所以最终的结果也是近似最优解(这个案例上就是最优解)。

案例二（哈夫曼编码）

哈夫曼编码指的是由哈夫曼提出的一种编码方式，他完全依据字符出现的频率来构造一种平均长度最短的编码。也称作最佳编码。而这种编码方式，也属于贪心算法的一项比较典型的应用，他主要应用于文件压缩领域。
我们知道ASCII 一共有128个字符，因此，如果要保存这些字符，最少要占用log128个bit。同理，如果字符个数为C，至少要占用logC个Bit。举个简单的例子：假如有一个文件，只包含一些字符：a,e,i,s,t，并且加上一些空格和newline(换行)，一共7种字符，所以每个字符最少占用log7个bit，也就是3个bit，如图所示，假如一共有58个字符，因此所有字符加起来最少需要占用3*58=174个比特空间。

字符	编码	频率	比特数
a	000	10	30
e	001	15	45
i	010	12	36
s	011	3	9
t	100	4	12
空格	101	13	39
newline	111	1	3
总计			174

如果要对这些数据进行压缩，有什么简单的办法吗？答案就是哈夫曼编码。他能够使得一些普通的文件普遍节省25%的空间，甚至能够使得一些大型文件节省百分之五十到七十的空间。而他的策略就是更具字符出现的频率，让每个字符占用大小不一的空间。需要注意的一点就是，如果所有字符出现的频率是一样的话，那么对于占用空间的压缩是不存在的。
如下图所示，我们可以通过二叉树来表示字母的二进制。
数据结构如下图所示：

WX20190312-174253@2x.png

该二叉树需要具有如下特点：

节点要么是叶子结点，要么必须有两个子节点
字符数据都是放在叶子结点上面
从根节点开始，用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，初步看来并没有节省太大的空间，这是因为上图中的二叉树并不是最优前缀码。如下图所示，如果改为最优前缀码之后，效果如图所示，一共节省了174-146=28个字符。

WX20190312-175756@2x.png

怎么生成最优前缀码，其实用的就是哈夫曼算法，我们可以把每个字符出现的频率当作他的权值，权值越大，出现的频率越高。他可以描述为：首先通过权值最低的两个结点生成一个新的父节点，新的父节点的权值等于他的子节点的权值之和，并命名为T1，之后再在剩余的节点和T1中查找出权值最低的两个节点，生成新的父节点，直到所有节点都生成一棵新的二叉树，则这颗新的二叉树就是最优二叉树，也叫最优前缀码。以上面的字符数据为例：

初始状态：

截图.png

第一步：
由于s和nl出现的频率最低，通过s和nl生成新的二叉树节点，新的节点权值=s(权值)+nl(权值) = 4

截图1.png

第二步：
由于T1和t现在权值最低，因此，T1和t生成新的二叉树节点T2，T2的权值为8。

截图2.png

第三步：由于T2和a现在为权值最低的两个节点，把他生成新的二叉树节点T3,T3的权值为18.

截图.png

第四步：剩下的i和sp为权值最低的两个点了，把i和sp生成新的二叉树节点T4,T4的权值为25.

截图.png

第五步：e和T3生成新的节点T5,T5的权值为33.

截图.png

第六步：只剩下T4和T5两个节点了，把T4,T5生成新的节点T6，他的权值为58，第六步后，也是最后一步生成的二叉树也是最终的二叉树，他也被称为最优二叉树。

截图.png

具体代码实现

定义节点的数据结构Node.class

public class Node implements Comparable<Node>{
    private int primary; //节点的权值
    private Node leftNode; //节点的左子节点
    private Node rightNode; //节点的右子节点
    private char value; //节点代表的字符

    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'};//字符数组
 int[] fraq = {10,15,12,3,4,13,1}; //字符对于出现频率
 Map<String,String> enCodeMap = new HashMap<>(); //保存不同字符对应的路径
 LinkedList<Node> list = new LinkedList<>(); //保存初始化的节点列表

初始化数据结构：

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

构建二叉树

  private void buildTree(){
        while(list.size() > 1){
            //取出出现频率最低的两个节点
            Node node1 = list.get(0);
            Node node2 = list.get(1);
            //生成新节点
            Node newNode = new Node(node1.getPrimary()+node2.getPrimary());
            //设置新节点左右子树
            newNode.setLeftNode(node1);
            newNode.setRightNode(node2);
            //从数组中移除频率最低的两个节点
            list.remove(0);
            list.remove(0);
            //新的节点按照出现频率从低到高的原则插入列表
            addNewNodeToList(newNode);
        }
    }

新节点插入

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

获取最优二叉树的路径

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");
        }
}

打印最终结果

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");
        }
    }

打印结果:

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

重新计算占用空间：

字符	编码	频率	比特数
a	111	10	30
e	10	15	30
i	00	12	24
s	11001	3	15
t	1101	4	16
空格	01	13	26
newline	11000	1	5
总计			146

案例三（纸币找零问题）

假如有1元、2元、5元、10元的纸币，如果要找16块钱零钱，正常只需要1张10元+1张5元+1张1元纸币 = 16，而这肯定也是最优的解决方案。他的策略是要凑够目标数字,用文字描述如下就是，永远先找最大的纸币，判断是否超过目标值，超过则换下一张最大的纸币，知道凑够的纸币值等于目标值。而这种策略也被叫贪心算法。
但是这种策略不一定每次都保证有效，比如对于1、5、7元纸币，比如说要凑出10元，如果优先使用7元纸币，则张数是4张，（1+1+1+7），而真正的最优解是5+5=10，2张。

总结

贪心算法试图通过局部最优解找到整体最优解
最终得到的可能是最终最优解，但也有可能是近似最优解
贪心算法大部分情况下易于实现，并且效率不错

文章引用：

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