贪心算法(贪婪算法)

一时失言乱红尘 2023-10-04 18:35 63阅读 0赞

贪心算法(贪婪算法)

#### 文章目录 ####

*   *   *  \*\*贪心算法思想\*\*
         *  选择排序
         *  平衡字符串
         *  买卖股票的最佳时机
         *  跳跃游戏
         *  钱币找零
         *  多机器调度问题
         *  举办活动数量最多
         *  无重叠区间

#### **贪心算法思想** ####

1.贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，**不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解**。  
2.贪心选择是指所求问题的**整体最优解可以通过一系列局部最优的选择**，即贪心选择来达到。这是贪心算法可行的第一个基本要素。  
3.当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。**问题的最优子结构性质是该问题可用贪心算法求解的关键特征**。贪心算法的每一次操作都对结果产生直接影响。贪心算法对每个子问题的解决方案都做出选择，**不能回退**。  
4.贪心算法的基本思路是**从问题的某一个初始解出发一步一步地进行**，根据某个优化测度，**每一步都要确保能获得局部最优解**。每一步只考虑一个数据，他的选取应该满足局部优化的条件。**若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中**，直到把所有数据枚举完，或者不能再添加算法停止。  
5.实际上，**贪心算法适用的情贪心算法(贪婪算法)况很少**。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。

**该算法存在的问题**  
1.**不能保证求得的最后解是最佳的**  
2.**不能用来求最大值或最小值的问题**  
3.**只能求满足某些约束条件的可行解的范围**

#### 选择排序 ####

**我们熟知的选择排序，其实采用的即为贪心策略。**

它所采用的贪心策略即为每次从未排序的数据中选取最小值，并把最小值放在未排序数据的起始位置，直到未排序的数据为0，则结束排序。

import java.util.Arrays;
    /**
     * 选择排序
     */
    public class TestDemo {
        
        public static void swap(int[] arr, int i, int j){
        
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        public static void selectSort(int[] arr){
        
            //i: 未排序数据的起始位置
            for(int i = 0; i < arr.length; ++i)
            {
        
                int minIdx = i;
            //从所有未排序的数据中找最小值的索引
                for(int j = i + 1; j < arr.length; ++j){
        
                    if(arr[j] < arr[minIdx])
                        minIdx = j;
                }
                swap(arr, minIdx, i);
            }
        }
        public static void main(String[] args) {
        
            int[] arr = {
        10, 3, 6, 0, 8};
            selectSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

![在这里插入图片描述][7309ccc97e8040d287b7918958a7bef8.png_pic_center]

#### 平衡字符串 ####

https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/

在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。

返回可以通过分割得到的平衡字符串的 最大数量 。

输入：s = `"RLLLLRRRLR"`  
输出：3  
解释：s 可以分割为 `"RL"、"LLLRRR"、"LR"` ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。

解题思路: 不要有嵌套的平衡，只要达到平衡，就立即分割(贪心策略).我们假设 ‘R’ == 1, ‘L’ == -1 .只要累加等于 0 就算分割一次.

![在这里插入图片描述][0a41a2ed36ab4e4a8cb74b0a14101088.png_pic_center]

class Solution {
        
        public int balancedStringSplit(String s) {
        
            int cnt = 0;
            int balance = 0;
            for(int i = 0; i < s.length(); i++){
        
                if(s.charAt(i) == 'L')
                    balance--;
                if(s.charAt(i) == 'R')
                    balance++;
                if(balance == 0)
                    cnt++;
            }
            return cnt;
        }
    }

#### 买卖股票的最佳时机 ####

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

给你一个整数数组 prices ，其中 prices\[i\] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

![在这里插入图片描述][343d2a50cbcf4ca38292ff8a0cd60b74.png_pic_center]

class Solution {
        
        public int maxProfit(int[] prices) {
        
            int ret = 0;
            for(int i = 1; i < prices.length; ++i)
            {
        
                int curProfit = prices[i] - prices[i - 1];
                if(curProfit > 0)
                    ret += curProfit;
            }
            return ret;
        }
    }

#### 跳跃游戏 ####

https://leetcode-cn.com/problems/jump-game/

给定一个非负整数数组 `nums` ，你最初位于数组的 **第一个下标** 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

**贪心策略**  
设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x + `nums[x]`，这个值大于等于 y，即 `x+nums[x] ≥ y`，那么位置y也可以到达。  
这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置x，如果它在 最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以`x+nums[x]`更新 最远可以到达的位置。  
在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回True作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

![在这里插入图片描述][07853d45fca6409ab509dbe3a1d47fc3.png_pic_center]  
![在这里插入图片描述][e0d563e7beee4febad41edfb5797c524.png_pic_center]

/**
     * 跳跃位置
     */
    public class TestDemo3 {
        
        public class Solution {
        
            public boolean canJump(int[] nums) {
        
                int pos = nums.length - 1;
                int rightmost = 0;
                for (int i = 0; i <= pos; ++i) {
        
                    //如果可以到达当前位置，则更新最大
                    if (i <= rightmost) {
        
                        //每次更新最大的位置
                        rightmost = Math.max(rightmost, i + nums[i]);
                        //如果可以到达最后一个位置，则直接返回
                        if (rightmost >= pos) {
        
                            return true;
                        }
                    }
                }
                return false;
            }
        }
    }

#### 钱币找零 ####

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有`c0, c1, c2, c3, c4, c5, c6`张。现在要用这些钱来支付K元，至少要用多少张纸币？

**贪心策略**: 用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可.

import java.util.Scanner;
    /**
     * 纸币找零
     */
    public class TestDemo4 {
        
        public static int solve(int money, int[][] moneyCount)
        {
        
            int num = 0;
            //首先选择最大面值的纸币
            for (int i = moneyCount.length - 1; i >= 0; i--)
            {
        
                //需要的当前面值与面值数量取最小
                int c = Math.min(money / moneyCount[i][0], moneyCount[i][1]);
                money = money - c * moneyCount[i][0];
                num += c;
            }
            if (money > 0)
                num = -1;
            return num;
        }
        public static void main(String[] args) {
        
            //存放纸币与数量: first:纸币，second:数量
            int[][] moneyCount = {
         {
         1, 3 }, {
         2, 1 }, {
         5, 4 }, {
         10, 3 }, {
         20, 0 }
                    ,{
        50, 1}, {
         100, 10 } };
            Scanner scanner = new Scanner(System.in);
            int money;
            System.out.println("请输入要支付的钱");
            money = scanner.nextInt();
            int res = solve(money, moneyCount);
            if (res != -1)
                System.out.println(res);
            else
                System.out.println("No");
        }
    }

#### 多机器调度问题 ####

某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间  
输入:  
第一行T（1<T<100)表示有T组测试数据。每组测试数据的第一行分别是整数n，m（1<=n<=10000，  
1<=m<=100），接下来的一行是n个整数ti（1<=t<=100)。  
输出: 所需的最短时间

**贪心策略: 每次选取剩余作业中执行时间最长的,然后分别优先给先完成的机器分配新的任务**

![在这里插入图片描述][5ed281f227ef43d3a408de979056d76a.png_pic_center]

import java.util.Arrays;
    import java.util.Scanner;
    /**
     *多机器调度问题
     */
    public class TestDemo5 {
        
        public static int findMax(int[] machines){
        
            int ret = machines[0];
            for (int cur : machines)
            {
        
                if (ret < cur)
                    ret = cur;
            }
            return ret;
        }
        private static int greedStrategy(int[] taskTime, int m) {
        
            int n = taskTime.length;
            // 按作业时间从小到大排序
            Arrays.sort(taskTime);
            int[] machines = new int[m];
            // 作业数如果小于机器数，直接返回最大的作业时间
            if (n <= m) {
        
                return taskTime[n-1];
            } else {
        
                for (int i = n-1; i >= 0; --i) {
        
                    // 找到最先结束的机器,分配新的任务
                    int finish = 0;
                    //首先假设用第一个机器处理
                    int machineTime = machines[finish];
                    // 从剩余机器中选择作业时间最小的
                    for (int j = 1; j < m; j++) {
        
                        if (machineTime > machines[j]) {
        
                            finish = j;
                            machineTime = machines[j];
                        }
                    }
                    // 将新的任务分配给最先结束的机器执行
                    machines[finish] += taskTime[i];
                }
                // 从所有机器中选出最后执行完作业的机器
                return findMax(machines);
            }
        }
        public static void main(String[] args) {
        
            int n, m;
            System.out.println("请输入作业个数和机器数");
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            m = scanner.nextInt();
            System.out.println("输入任务的时间");
            int[] taskTime = new int[n];
            for (int i = 0; i < n; ++i){
        
                taskTime[i] = scanner.nextInt();
            }
            System.out.println("最短的时间" + greedStrategy(taskTime,m));
        }
    }

#### 举办活动数量最多 ####

有n个需要在同一天使用同一个教室的活动 `a1, a2`, …, an，教室同一时刻只能由一个活动使用。每个活动a\[i\]都有一个开始时间s\[i\]和结束时间f\[i\]。一旦被选择后，活动a\[i\]就占据半开时间区间\[s\[i\],f\[i\])。如果\[s\[i\],f\[i\])和\[s\[j\],f\[j\])互不重  
叠，a\[i\]和a\[j\]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。

![在这里插入图片描述][9901804ed2b9402cb82d80acf7a8c086.png_pic_center]

import java.util.Arrays;
    import java.util.Comparator;
    import java.util.Scanner;
    
    /**
     * 举办活动数量最多的
     */
    class myComparator implements Comparator<int[]> {
        
        //按起点递增排序
        public int compare(int[] a, int[] b) {
        
            return a[1] - b[1];
        }
    }
    public class TestDemo6 {
        
        public static int greedyActivitySelector(int[][] act)
        {
        
            //贪婪策略：每次选择最早结束的活动
            int num = 1, i = 0;
            for (int j = 1; j < act.length; j++)
            {
        
                if (act[j][0] >= act[i][1])
                {
        
                    i = j;
                    num++;
                }
            }
            return num;
        }
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int number = scanner.nextInt();
            int[][] act = new int[number][2];
            for (int i = 0; i < act.length; ++i)
            {
        
                act[i][0] = scanner.nextInt();
                act[i][1] = scanner.nextInt();
            }
            //按照活动截止时间从小到大排序
            Arrays.sort(act, new myComparator());
            int ret = greedyActivitySelector(act);
            System.out.println(ret);
        }
    }

#### 无重叠区间 ####

https://leetcode-cn.com/problems/non-overlapping-intervals/

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

**解法1: 先求出能得到最多的数量(上一题举办活动数量最多的思路),再总数相减,得到需要移除数量最少的值**

class myComparator implements Comparator<int[]> {
        
        //按最早结束递增排序
        public int compare(int[] a, int[] b) {
        
            return a[1] - b[1];
        }
    }
    class Solution {
        
        public int eraseOverlapIntervals(int[][] intervals) {
        
            if (intervals.length == 0) {
        
                return 0;
            }
            //按照结束进行递增排序
            Arrays.sort(intervals, new myComparator());
            //贪婪策略：每次选择最早结束的活动
            int num = 1, i = 0;
            for (int j = 1; j < intervals.length; j++)
            {
        
                if (intervals[j][0] >= intervals[i][1])
                {
        
                    i = j;
                    num++;
                }
            }
            return intervals.length - num;
        }
    }

解法2:

![在这里插入图片描述][f6cc12ea4c7d4a5eb4a9f358a04ff00a.png_pic_center]

class myComparator implements Comparator<int[]> {
        
        //按起点递增排序
        public int compare(int[] a, int[] b) {
        
            return a[0] - b[0];
        }
    }
    class Solution {
        
        public int eraseOverlapIntervals(int[][] intervals) {
        
            if (intervals.length == 0) {
        
                return 0;
            }
            //按照起始进行递增排序
            Arrays.sort(intervals, new myComparator());
            //贪婪策略：每次选择最早结束的活动
            int num = 0, i = 0;
            for (int j = 1; j < intervals.length; j++)
            {
        
                if (intervals[j][0] >= intervals[i][1])
                {
        
                    //下一场活动开始时间大于等于上一场活动结束时间
                    //不需要更新
                    i = j;
                }else{
        
                    if(intervals[j][1] < intervals[i][1])
                    {
        
                        //下一场活动结束时间小于上一场活动结束时间
                        //更新位置,把上一场删除
                        i = j;
                    }
                    ++num;
                }
            }
            return num;
        }
    }

**如果觉得学到了点有用知识,可以点赞三连嘛.我们一起进步!**

[7309ccc97e8040d287b7918958a7bef8.png_pic_center]: https://img-blog.csdnimg.cn/7309ccc97e8040d287b7918958a7bef8.png#pic_center
[0a41a2ed36ab4e4a8cb74b0a14101088.png_pic_center]: https://img-blog.csdnimg.cn/0a41a2ed36ab4e4a8cb74b0a14101088.png#pic_center
[343d2a50cbcf4ca38292ff8a0cd60b74.png_pic_center]: https://img-blog.csdnimg.cn/343d2a50cbcf4ca38292ff8a0cd60b74.png#pic_center
[07853d45fca6409ab509dbe3a1d47fc3.png_pic_center]: https://img-blog.csdnimg.cn/07853d45fca6409ab509dbe3a1d47fc3.png#pic_center
[e0d563e7beee4febad41edfb5797c524.png_pic_center]: https://img-blog.csdnimg.cn/e0d563e7beee4febad41edfb5797c524.png#pic_center
[5ed281f227ef43d3a408de979056d76a.png_pic_center]: https://img-blog.csdnimg.cn/5ed281f227ef43d3a408de979056d76a.png#pic_center
[9901804ed2b9402cb82d80acf7a8c086.png_pic_center]: https://img-blog.csdnimg.cn/9901804ed2b9402cb82d80acf7a8c086.png#pic_center
[f6cc12ea4c7d4a5eb4a9f358a04ff00a.png_pic_center]: https://img-blog.csdnimg.cn/f6cc12ea4c7d4a5eb4a9f358a04ff00a.png#pic_center