跟左神学算法9 经典算法

内容：

1、贪心算法介绍

2、贪心算法实例

1、贪心算法介绍

什么是贪心策略(贪心算法)：

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关

贪心策略是否正确：

贪心策略的正确性的证明，不要纠结这个，只用去记住这个策略的使用即可在写代码的时候一般使用对数器去验证贪心策略是否有效，

这是以为贪心策略的证明几乎是不可能的，很难去证明策略的有效性

贪心策略使用方法：

不断尝试各种贪心策略，先写一个绝对对的(很暴力的算法去算)，用对数器与你写的各种贪心策略比较，选择正确率最好的一种贪心策略，也就是用对数器去验证你写的贪心策略

2、贪心算法实例

实例1 切分金条

问题描述：

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？

例如给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60  金条要分成10,20,30三个部分

如果， 先把长 度60的金条分成10和50，花费60再把长度50的金条分成20和30， 花费50 一共花费110铜板

但是如果先把长度60的金条分成30和30，花费60 再把长度30 金条分成10和20，花费30 一共花费90铜板

输入一个数组，返回分割的最小代价

贪心策略：哈夫曼编码

代码：

public class LessMoney {
    public static int lessMoney(int[] arr) {
        // PriorityQueue => min heap(default) 
        PriorityQueue<Integer> pQ = new PriorityQueue();
        // init the heap
        for (int i = 0; i < arr.length; i++) {
            pQ.add(arr[i]);
        }
        int sum = 0;
        int cur = 0;
        // cal the sum
        while (pQ.size() > 1) {
            cur = pQ.poll() + pQ.poll();
            sum += cur;
            pQ.add(cur);
        }
        return sum;
    }
        
    public static void main(String[] args) {
        // solution:
        int[] arr = { 10, 20, 30 };
        System.out.println(lessMoney(arr));
        
        int[] arr2 = { 6, 7, 8, 9 };
        System.out.println(lessMoney(arr2));
    }
}

实例2 - 成本收益

问题描述：

输入：

• 参数1，正数数组costs costs[i]表示i号项目的花费
• 参数2，正数数组profits profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
• 参数3，正数k k表示你不能并行、只能串行的最多 做k个项目 => 最多能做的项目数
• 参数4，正数m m表示你初始的资金

说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目(一次只能做一个项目)
输出： 你最后获得的最大钱数

贪心策略：

做能做的项目(costs<m)中的收益(profits)最大的项目
用两个堆 一个小根堆(花费) 一个大根堆(收益) ，每次从小根堆中不断拿出能做的项目，然后在大根堆中每次拿出一个收益最大的项目

代码：

public class IPO {            
    public static class Node {
        public int p;
        public int c;
        public Node(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }
        
    public static class MinCostComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.c - o2.c; // 升序
        }
    }
        
    public static class MaxProfitComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o2.p - o1.p; // 降序
        }
    }
        
    public static int findMaximizedCapital(int k, int w, int[] profits,
            int[] capital) {
        // init nodes
        Node[] nodes = new Node[profits.length];
        for (int i = 0; i < profits.length; i++) {
            nodes[i] = new Node(profits[i], capital[i]);
        }
        // init heap
        PriorityQueue<Node> minCostQ = new PriorityQueue<Node>(nodes.length,
                new MinCostComparator());        // min heap
        PriorityQueue<Node> maxProfitQ = new PriorityQueue<Node>(nodes.length,
                new MaxProfitComparator());        // max heap
        for (int i = 0; i < nodes.length; i++) {
            minCostQ.add(nodes[i]);
        }
        for (int i = 0; i < k; i++) {
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= w) {
                maxProfitQ.add(minCostQ.poll());
            }
            if(maxProfitQ.isEmpty()){
                return w;
            }
            w += maxProfitQ.poll().p;
        }
        return w;
    }
}

贪心实例3 - 最低字典序问题

问题描述：

给定一个字符串类型的数组strs，找到一种拼接方式，使得把所有字符串拼起来之后形成的字符串具有最低的字典序

贪心策略:

1、str1 <= str2 str1放前面否则str2放前面 这种是错误的   eg: str1 = b str2 = ba 此时bba>bab
2、str1 + str2 <= str2 + str1 str1放前面否则str2放前面    这种策略是正确的
上面的策略都是比较策略，比较策略一定要具有传递性才能被使用

代码：

public class LowestLexicography {
    // comparator
    public static class Mycomparator implements Comparator<String>{
        @Override
        public int compare(String a, String b) {
            return (a+b).compareTo(b+a);
        }
    }
    
    public static String lowestString(String[] strs){
        if(strs==null||strs.length==0){
            return "";
        }
        Arrays.sort(strs, new Mycomparator());
        String res = "";
        for(int i=0; i<strs.length; i++){
            res += strs[i];
        }
        return res;
    }
    
    public static void main(String[] args) {
        String[] strs1 = {"jibw", "ji", "jp", "bw", "jibw"};
        System.out.println(lowestString(strs1));
        
        String[] strs2 = {"b", "ba"};
        System.out.println(lowestString(strs2));
    }
}

贪心实例4 - 会议室安排

问题描述：

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，

你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次

贪心策略: 选最早结束的项目 然后淘汰掉和最早结束的项目冲突的项目

代码：

public class BestArrange {
    public static class Program {
        public int start;
        public int end;

        public Program(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static class ProgramComparator implements Comparator<Program> {
        @Override
        public int compare(Program p1, Program p2) {
            return p1.end - p2.end;        // 升序
        }
    }

    public static int bestArrange(Program[] programs, int cur) {
        Arrays.sort(programs, new ProgramComparator());
        int result = 0;
        for (int i = 0; i < programs.length; i++) {
            if (cur <= programs[i].start) {
                result++;
                cur = programs[i].end;
            }
        }
        return result;
    }
}