贪心算法例题

哈夫曼编码

现在要解决这么一个问题，假设有一根长度为n的金条，要切成[x,y,z,....](x+y+z+....=n)的长度，并且每次切都要花费当前长度的代价，问：怎么切代价最小

举个例子：假设金条长度为60，要切成[10,20,30]的，如果我先把金条切成[10,50]，那么花费就是60，然后再将50切成[20,30]，花费是50，最后加起来总花费就是110，如果用另一种方法，先切成[30,30]，花费是60，然后将30切成[10,20]，花费是30，最后花费总和就是90，这种方法的代价是最小的

题解

典型的哈夫曼编吗问题。构建一个小根堆，将所有要求的值放进去，然后依次取出两个值，将其和累加到代价中，并且将其和再次放入小根堆，不断执行此操作直到堆中元素不大于1

代码

import java.util.*;

public class Main {
    public static int lessMoney(int[] arr) {
        PriorityQueue<Integer> minMoney = new PriorityQueue<>();
        for(int i:arr)
            minMoney.add(i);
        int sum = 0;
        while(minMoney.size() > 1) {
            int a = minMoney.poll();
            int b = minMoney.poll();
            int c = a + b;
            sum += c;
            minMoney.add(c);
        }
        return sum;
    }
    public static void main(String[] args) {
        System.out.println(lessMoney(new int[] {10,20,30}));
    }
}

给定一个字符串数组，要求将其拼接后字典序最小

题解

假设字符串数组是str[] = {"ab","cd","ef"}，很明显答案就是”abcdef“最小，其实这是一道贪心问题，我的想法是将字符串数组进行内的字符串数组进行排序，这个大思路是没错的，但问题是怎么排序，str[i] < str[j]?这样其实不行，举个反例str[] = {"b","ba"}，如果按照那个贪心策略排序，得到的答案是"bba"，但实际上“bab”更小，后来仔细以想，贪心策略应该是str[i] + str[j] < str[j] + str[i]，有兴趣的大家可以下去证明，还是比较好证的

代码

import java.util.*;

public class Main {
    public static class MyCompara implements Comparator<String> {
        public int compare(String s1, String s2) {
            String tmp1 = s1 + s2;
            String tmp2 = s2 + s1;
            return tmp1.compareTo(s2);
        }
    }
    public static String minString(String[] str) {
        String res = "";
        Arrays.sort(str,new MyCompara());
        for(int i = 0;i < str.length;i++)
            res += str[i];
        return res;
    }
    public static void main(String[] args) {
        System.out.println(minString(new String[] {"ab","ef","cd"}));
    }
}

题目链接：LeetCode502

题解

这道题贪心策略很直白，首先定义出一个结构，结构中包含利润和成本，然后按照成本最低构建一个小根堆，按照利润最高构建一个大根堆，依次将小根堆中成本小于等于当前资金的项目都添加到大根堆去，然后依次将大根堆中的项目弹出，获取利润即可

代码

class Solution {
    class Node {
        int c;//成本
        int p;//利润
        Node(int c,int p) {
            this.c = c;
            this.p = p;
        }
    }
    
    public static class MinC implements Comparator<Node> {
        public int compare(Node node1,Node node2) {
            return node1.c - node2.c;
        }
    }
    
    public static class MaxP implements Comparator<Node> {
        public int compare(Node node1,Node node2) {
            return node2.p - node1.p;
        }
    }
        
    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        PriorityQueue<Node> minQueue = new PriorityQueue<>(new MinC());
        PriorityQueue<Node> maxQueue = new PriorityQueue<>(new MaxP());
        Node[] node = new Node[Profits.length];
        
        for(int i = 0;i < Profits.length;i++) {
            node[i] = new Node(Capital[i],Profits[i]);
            minQueue.add(node[i]);
        }
        
        for(int i = 0;i < k;i++) {
            while(!minQueue.isEmpty() && minQueue.peek().c <= W)
                maxQueue.add(minQueue.poll());
            if(maxQueue.isEmpty())//资金永远不够做某个项目
                return W;
            W += maxQueue.poll().p;
        }
        return W;
    }
}

题目链接：51Nod1428

题解

三种贪心策略，按照开始时间小的，按照结束时间小的，按照总的时间短的，事实证明按照结束时间小的进行贪心的策略是对的

代码

import java.util.*;
class Node {
    int start;
    int end;
    Node(int start,int end) {
        this.start = start;
        this.end = end;
    }
}
public class Main {
    
    public static class MyCompare implements Comparator<Node> {
        public int compare(Node node1,Node node2) {
            return node1.end - node2.end;
        }
    }
    
    public static int bestArray(Node[] node,int start) {
        Arrays.sort(node,new MyCompare());
        int sum = 0;;
        for(int i = 0;i < node.length;i++) {
            if(start <= node[i].start) {
                sum++;
                start = node[i].end;
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        Node[] node = new Node[n];
        for(int i = 0;i < n;i++) {
            int start = cin.nextInt();
            int end = cin.nextInt();
            node[i] = new Node(start,end);
        }
        System.out.println(bestArray(node,-10000));
    }
}