MENU

贪心算法例题

August 10, 2018 • Read: 3500 • 算法阅读设置

哈夫曼编码

现在要解决这么一个问题,假设有一根长度为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));
    }
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code