贪心算法实战

╰+攻爆jí腚メ 2024-04-08 12:00 64阅读 0赞

## 贪心算法实战 ##

> 贪心算法就是按照我们人类最想要的想法去完成某件事情（每次都尝试找到局部最优解）  
> 贪心算法只适用于某些特定的算法题，并且不好证明【用对数器验证】

### 1.点灯问题 ###

给定一个字符串str，只由‘X’和‘.’两种字符构成。
    ‘X’表示墙，不能放灯，也不需要点亮
    ‘.’表示居民点，可以放灯，需要点亮
    如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮
    返回如果点亮str中所有需要点亮的位置，至少需要几盏灯

#### 1.1 思路 ####

按照人类自然最正常的想法去就行：  
遇到墙，直接跳过  
①灯 墙（只能点灯）  
②灯 灯 墙（只能点灯，随便点哪一个）  
③灯 灯 灯（点最中间的）

#### 1.2 代码 ####

//贪心算法求解
    public static int minLight2(String road) {
        
        char[] arr = road.toCharArray();
        int i = 0;
        int lights = 0;
        while (i < arr.length) {
        
            if (arr[i] == 'X') {
        
                i++;
            } else {
        
                lights++;
                if (i + 1 == arr.length) {
        
                    break;
                } else {
        
                    if (arr[i + 1] == 'X') {
        
                        //灯 墙
                        i += 2;
                    } else {
        
                        //灯 灯 灯
                       i += 4;
                    }
                }
            }
        }
        return lights;
    }

### 2.分割的最小代价 ###

金条切成两半，是需要花费和长度数值一样的铜板的。
    比如长度为20的金条，不管怎么切，都要花费20个铜板。 一群人想整分整块金条，怎么分最省铜板? 
    
    例如,给定数组{
        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铜板。
    输入一个数组，返回分割的最小代价。

#### 2.1 思路 ####

> 构建哈夫曼树【利用小根堆】  
> 将arr数组中的值全部入堆，每次从堆中弹出两个，然后组合成新的，继续入堆

#### 2.2 代码 ####

public static int lessMoney2(int[] arr){
        
        PriorityQueue<Integer> smallHeap = new PriorityQueue<>();
        for(int i : arr){
        
            smallHeap.add(i);
        }
        int sum = 0;
        int cur = 0;
        while(smallHeap.size() > 1){
        
            cur = smallHeap.poll() + smallHeap.poll();
            sum += cur;
            smallHeap.add(cur);
        }
        return sum;
    }

### 3.会议室宣讲（最多宣讲场次） ###

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
    给你每一个项目开始的时间和结束的时间
    你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。
    返回最多的宣讲场次。

#### 3.1 思路 ####

> 项目结束早的先遍历

#### 3.2 代码 ####

public static int bestArrange2(Program[] programs){
        
        Arrays.sort(programs, new ProgramComparator());
        //当前时间线
        int timeLine = 0;
        int result = 0;
        //依次遍历会议，结束时间早的在前
        for(int i = 0; i < programs.length; i++){
        
            if(timeLine <= programs[i].start){
        
                result++;
                timeLine = programs[i].end;
            }
        }
        return result;
    }
    
    public static class ProgramComparator implements Comparator<Program>{
        
        //会议结束早的在前
        @Override
        public int compare(Program o1, Program o2) {
        
            return o1.end - o2.end;
        }
    }

### 4.做项目的最大收益 ###

输入: 正数数组costs、正数数组profits、正数K、正数M
    costs[i]表示i号项目的花费
    profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
    K表示你只能串行的最多做k个项目
    M表示你初始的资金
    说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
    输出：你最后获得的最大钱数。

#### 4.1 思路 ####

> 构建大根堆与小跟堆【堆：完全二叉树】

首先先找到花费最小的（因为可能启动资金不够），然后在花费小的里面找到利润最大的

#### 4.2 代码 ####

/**
     * 项目的最大收益
     */
    public class IPODemo {
        
        
        public static class Program {
        
            public int p;
            public int c;
    
            public Program(int p, int c) {
        
                this.p = p;
                this.c = c;
            }
        }
        
        // 最多K个项目
        // W是初始资金
        // Profits[] Capital[] 一定等长
        // 返回最终最大的资金
        public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
        
            //小根堆【花费小】
            PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
            //大根堆【利润大】
            PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
            for(int i = 0; i < Profits.length; i++){
        
                minCostQ.add(new Program(Profits[i], Capital[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;
        }
    
    
        //构建比较器[按照项目的花销小排序]
        public static class MinCostComparator implements Comparator<Program>{
        
    
            @Override
            public int compare(Program o1, Program o2) {
        
                return o1.c - o2.c;
            }
        }
    
        //按照利润大排序
        public static class MaxProfitComparator implements Comparator<Program>{
        
    
            @Override
            public int compare(Program o1, Program o2) {
        
                return o2.p - o1.p;
            }
        }
    }

### 5 总结： ###

贪心算法就是按照我们人类正常思维解决的一种算法，没有固定的模板或技巧，需要大量练习类似题目，积累经验。【常见解法：排序、堆】