算法 - 附案例（二分查找 | 分治算法 | 动态规划 | KMP算法 | 贪心算法）

ゝ一世哀愁。 2022-09-04 09:44 176阅读 0赞

### 文章目录 ###

*   *  二分查找算法(非递归)
     *  分治算法
     *  动态规划
     *  KMP算法
     *  贪心算法

## 二分查找算法(非递归) ##

介绍  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70]

代码实现：

数组 \{1,3, 8, 10, 11, 67, 100\}, 编程实现二分查找， 要求使用非递归的方式完成.。

/**
     * @author xdragon
     * @Description 二分查找的非递归实现
     * @createTime 2021年08月12日
     */
    public class BinarySearchNoRecur { 
        public static void main(String[] args) { 
            //测试
            int[] arr = { 1,3, 8, 10, 11, 67, 100};
            int index = binarySearch(arr,67);
            System.out.println("index = " + index);
        }
    
        /**
         * 二分查找的非递归实现
         * @param arr 待查找的数组，按升序排序
         * @param target 需要查找的数
         * @return 返回对应的下标，若不存在则为 -1
         */
        public static int binarySearch(int[] arr, int target){ 
            int left = 0;
            int right = arr.length - 1;
            while (left <= right){ 
                int mid = (left + right) / 2; //中间值下标
                if (arr[mid] == target){ // 相等就直接返回
                    return mid;
                }else if (arr[mid] > target){ //在左边查找
                    right = mid - 1;
                }else { //在右边查找
                    left = mid + 1;
                }
            }
            return -1; //没有找到就返回-1
        }
    }

67查找成功，返回该数的下标5  
![在这里插入图片描述][a8b77a215cce4dd4bfee2271ca0c89d2.png]

## 分治算法 ##

介绍：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 1]

--------------------

分治算法的基本步骤

分治法在每一层递归上都有三个步骤：

1.  分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2.  解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3.  合并：将各个子问题的解合并为原问题的解。

--------------------

分治算法最佳实践-汉诺塔  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 2]  
汉诺塔游戏的演示和思路分析：  
1)如果是有一个盘， A->C

如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘  
2) 先把 最上面的盘 A->B  
3) 把最下边的盘 A->C  
4) 把 B 塔的所有盘 从 B->C

/**
     * @author xdragon
     * @Description 分治算法
     * @createTime 2021年08月12日
     */
    public class Hanoitower { 
        public static void main(String[] args) { 
            //测试
            hanoiTower(3,'A','B','C');
        }
    
        /**
         * 分治算法 - 汉诺塔的移动的方法
         * @param num 多少个盘
         * @param a 开始
         * @param b 借助中间盘
         * @param c 目的
         */
        public static void hanoiTower(int num, char a, char b, char c){ 
            //如果只有一个盘，A -> C
            if (num == 1){ 
                System.out.println("第1个盘从 " + a + " -> " + c);
            }else { 
                // 1.先把最上面的所有盘移动到b，其中会借用到c
                hanoiTower(num - 1,a,c,b);
                // 2.把最下面的盘a到c
                System.out.println("第" + num + "个盘从 " + a + " -> " + c);
                //3. 把 B 塔的所有盘 从 b->c , 移动过程使用到 a 塔
                hanoiTower(num - 1,b,a,c);
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 3]

## 动态规划 ##

动态规划算法介绍：

1.  动态规划(Dynamic Programming)算法的核心思想是：将 大问题划分为小问题进行解决，从而一步步获取最优解  
    的处理算法
2.  动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这  
    些子问题的解得到原问题的解。
3.  与分治法不同的是，适合于用动态规划求解的问题，经分解得到 子问题往往不是互相独立的。 ( 即下一个子  
    阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
4.  动态规划可以通过填表的方式来逐步推进，得到最优解

--------------------

应用场景  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 4]  
解题思路：

算法的主要思想，利用动态规划来解决。每次遍历到的第 i个物品，根据 w\[i\]和 v\[i\]来确定是否需要将该物品放入背包中。即对于给定的 n个物品，设 **v\[i\]、w\[i\]分别为第 i个物品的价值和重量**，C为背包的容量。再令二维数组 `v[i][j]` 表示在前 i个物品中能够装入容量为 j的背包中的最大价值。

则我们有下面的结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 6]

图解的分析

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 7]

--------------------

动态规划-背包问题的代码实现

import java.util.Arrays;
    
    /**
     * @author xdragon
     * @Description TODO
     * @createTime 2021年08月13日
     */
    public class KnapsackProblem { 
        public static void main(String[] args) { 
            //各个物品的重量
            int[] weight = { 1, 4, 3};
            //各个物品的价值
            int[] value = { 1500, 3000, 2000};
            //背包最大的容量
            int maxSize = 4;
            //物品的个数
            int n = value.length;
            //最大价值
            int[][] maxValue = new int[n + 1][maxSize + 1];
            //装入的方式
            int[][] method = new int[n + 1][maxSize + 1];
    
            //初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是 0
            //maxValue.length 获取二维数组的行
            //maxValue[0].length 获取二维数组的列
            for (int i = 0; i < maxValue.length; i++) { 
                maxValue[i][0] = 0; //将第一列设置为 0
            }
            for (int i = 0; i < maxValue[0].length; i++) { 
                maxValue[0][i] = 0; //将第一行设置 0
            }
    
            //依次装入背包
            for (int i = 1; i < maxValue.length; i++) { 
                for (int j = 1; j < maxValue[0].length; j++) { 
                    //当准备装入的物品重量 大于 当前背包容量时，就直接使用上一个单元格的装入策略
                    if (weight[i - 1] > j) { 
                        maxValue[i][j] = maxValue[i - 1][j];
                    } else {   //准备装入的物品重量 小于 当前背包容量时
                        //剩下的容量
                        int remainWeight = j - weight[i - 1];
                        //如果放入该物品前的最大价值 大于 放入该物品后的最大价值，就不放入该物品
                        if (maxValue[i - 1][j] > value[i - 1] + maxValue[i - 1][remainWeight]) { 
                            maxValue[i][j] = maxValue[i - 1][j];
                        } else {  //放入该物品前的最大价值 小于 放入该物品后的最大价值，就记录到 方式 中
                            maxValue[i][j] = value[i - 1] + maxValue[i - 1][remainWeight];
                            //存入到 方式 中
                            method[i][j] = 1;
                        }
                    }
                }
            }
    
            //打印放入背包的最大价值
            for (int[] arr : maxValue) { 
                System.out.println(Arrays.toString(arr));
            }
    
            //打印价值最大的 方式
            //存放 方式 的二维数组的最大下标，从最后开始搜索存放方式
            int i = method.length - 1;
            int j = method[0].length - 1;
            while (i > 0 && j > 0) { 
                if (method[i][j] == 1) { 
                    System.out.println("将第 " + i + " 个物品放入背包中");
                    //背包剩余容量
                    j -= weight[i - 1];
                }
                i--;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 8]

## KMP算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 9]

算法应用——字符串匹配

思路及图解

问题：有一个字符串 str1= BBC ABCDAB ABCDABCDABDE，和一个子串 str2=ABCDABD。现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

--------------------

先看，暴力匹配实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 11]

--------------------

算法步骤

首先，用 str1的第一个字符和 str2的第一个字符去比较，不符合，关键词向后移动一位  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 12]  
重复第一步，还是不符合，再后移  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 13]  
一直重复，直到 Str1有一个字符与 Str2的第一个字符符合为止![在这里插入图片描述][d5a0c6206f1e4ef5920de31e461cf56e.png]  
接着比较字符串和搜索词的下一个字符，还是符合![在这里插入图片描述][c1ab1db83d1d4786980993d56d7db4cb.png]  
遇到 Str1有一个字符与 Str2对应的字符不符合![在这里插入图片描述][b59f4f7693684569827e81cd6e99cd24.png]  
**重要步骤**

这时候，想到的是继续遍历 str1的下一个字符，重复第 1步。(其实是很不明智的，因为此时 BCD已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”

KMP 算法的想法是：设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率

怎么做到把刚刚重复的步骤省略掉？可以对 str2计算出一张部分匹配表，这张表的产生在后面介绍

str2的部分匹配表如下  
![在这里插入图片描述][6f23b1e6f1b3496993a0695cd7e08505.png]  
已知空格与 D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的部分匹配值为 2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值  
因为 6 - 2 等于 4，所以将搜索词向后移动 4 位

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][f56d1d926df14a959c33f7ee65056d3a.png]  
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为 2（”AB”），对应的部分匹配值为0。

所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位

![在这里插入图片描述][4718d65e9b474d99885a6161d03561fb.png]  
因为空格与 A不匹配，继续后移一位  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 15]  
![在这里插入图片描述][7347b43710ad4b808b4c4ac9f513a5a7.png]  
逐位比较，直到发现 C与 D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动 4 位

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 16]  
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动 7 位，这里就不再重复了

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 17]  
**部分匹配表的生成**

**前缀与后缀**  
前缀：ABCD的前缀为\[A, AB, ABC\]  
后缀：ABCD的后缀为\[BCD, CD, D\]

部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 18]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 19]  
实现代码：

/**
     * @author xdragon
     * @Description TODO
     * @createTime 2021年08月13日
     */
    public class KMPAlgorithm { 
        public static void main(String[] args) { 
            //原字符串
            String str1 = "BBC ABCDAB ABCDABCDABDE";
            //子字符串
            String str2 = "ABCDABD";
            //匹配结果
            int result = getPosition(str1, str2);
            if (result != -1) { 
                System.out.print("匹配位置是：str1[" + result + "]");
            } else { 
                System.out.println("匹配失败");
            }
        }
    
        /**
         * 得到匹配字符串的部分匹配表
         *
         * @param matchStr 用于匹配的字符串
         * @return 部分匹配表
         */
        public static int[] getTable(String matchStr) { 
            //部分匹配值的数组
            int[] sectionTable = new int[matchStr.length()];
            //匹配字符串的第一个元素没有前缀与后缀，部分匹配值为0
            sectionTable[0] = 0;
            //i用来指向部分匹配字符串末尾的字符，j用来指向开始的字符
            for (int i = 1, j = 0; i < matchStr.length(); i++) { 
                //当j>0且前缀后缀不匹配时，使用部分匹配表中前一个表项的值
                while (j > 0 && matchStr.charAt(j) != matchStr.charAt(i)) { 
                    j = sectionTable[j - 1];
                }
    
                //如果前缀后缀匹配，j向后移，继续比较
                if (matchStr.charAt(j) == matchStr.charAt(i)) { 
                    j++;
                }
                //存入匹配值
                sectionTable[i] = j;
            }
            return sectionTable;
        }
    
        /**
         * 通过KMP算法匹配字符串，若匹配成功，返回第一个字符出现的位置
         *
         * @param str1 用于匹配的字符串
         * @param str2 要匹配的字符串
         * @return 第一个字符出现的位置，没有则返回-1
         */
        public static int getPosition(String str1, String str2) { 
            //获得str2的部分匹配表
            int[] sectionTable = getTable(str2);
            for (int i = 0, j = 0; i < str1.length(); i++) { 
                //两个字符匹配
                if (str1.charAt(i) == str2.charAt(j)) { 
                    j++;
                    if (j == str2.length()) { 
                        //如果匹配完成，返回第一个字符出现位置
                        return i - str2.length() + 1;
                    }
                } else { 
                    //如果匹配失败了，使用部分匹配表，跳转到str1对应位置
                    //如果j==0，说明没有字符被被匹配，直接让i指向str1的下一个字符
                    if (j == 0) { 
                        continue;
                    }
                    //跳转步数 = 已经匹配的字符个数 - 部分匹配表对应的值
                    int position = j - sectionTable[j - 1];
                    i += position;
                    //因为循环后会+1，所以此处i-1
                    i--;
                    //重置j，重新匹配
                    j = 0;
                }
            }
            return -1;
    
        }
    }

测试数据：

//原字符串
            String str1 = "BBC ABCDAB ABCDABCDABDE";
            //子字符串
            String str2 = "ABCDABD";

结果：  
![在这里插入图片描述][cf6ba93352074ca2a06044ae63225942.png]

## 贪心算法 ##

算法简介

*  贪心算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。
 *  贪心算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

**算法应用1——集合覆盖**：

假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 20]  
思路

*  遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系
 *  将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
 *  重复第 1步直到覆盖了全部的地区

图解

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 21]

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 22]  
遍历电台的覆盖地区，发现K1覆盖的地区最多，将K1覆盖的地区从地区集合中移除。然后将K1放入电台集合中，并更新覆盖地区个数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 23]

遍历，发现K2覆盖的地区最多，将K2覆盖的地区从地区集合中移除。然后将K2放入电台集合中，并更新覆盖地区个数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 24]

遍历，发现K3覆盖的地区最多，将K3覆盖的地区从地区集合中移除。然后将K3放入电台集合中，并更新覆盖地区个数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 25]  
遍历，发现K5覆盖的地区最多，将K5覆盖的地区从地区集合中移除。然后将K5放入电台集合中，并更新覆盖地区个数。所有区域都被覆盖，算法结束  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 26]

Java代码实现：

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    
    /**
     * @author xdragon
     * @Description 贪心算法 | 覆盖电台
     * @createTime 2021年08月13日
     */
    public class GreedyAlgorithm { 
        public static void main(String[] args) { 
            //创建广播电台,放入到 Map
            HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
            //将各个电台放入到 broadcasts
            HashSet<String> hashSet1 = new HashSet<String>();
            hashSet1.add("北京");
            hashSet1.add("上海");
            hashSet1.add("天津");
            HashSet<String> hashSet2 = new HashSet<String>();
            hashSet2.add("广州");
            hashSet2.add("北京");
            hashSet2.add("深圳");
            HashSet<String> hashSet3 = new HashSet<String>();
            hashSet3.add("成都");
            hashSet3.add("上海");
            hashSet3.add("杭州");
            HashSet<String> hashSet4 = new HashSet<String>();
            hashSet4.add("上海");
            hashSet4.add("天津");
            HashSet<String> hashSet5 = new HashSet<String>();
            hashSet5.add("杭州");
            hashSet5.add("大连");
            //加入到 map
            broadcasts.put("K1", hashSet1);
            broadcasts.put("K2", hashSet2);
            broadcasts.put("K3", hashSet3);
            broadcasts.put("K4", hashSet4);
            broadcasts.put("K5", hashSet5);
            //allAreas 存放所有的地区
            HashSet<String> allAreas = new HashSet<String>();
            allAreas.add("北京");
            allAreas.add("上海");
            allAreas.add("天津");
            allAreas.add("广州");
            allAreas.add("深圳");
            allAreas.add("成都");
            allAreas.add("杭州");
            allAreas.add("大连");
            //创建 ArrayList, 存放选择的电台集合
            ArrayList<String> selects = new ArrayList<String>();
            //定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区交集
            HashSet<String> tempSet = new HashSet<String>();
            //定义给 maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的 key
            //如果 maxKey 不为 null , 则会加入到 selects
            String maxKey = null;
            while (allAreas.size() != 0) {  // 如果 allAreas 不为 0, 则表示还没有覆盖到所有的地区
                //每进行一次 while,需要
                maxKey = null;
                //遍历 broadcasts, 取出对应 key
                for (String key : broadcasts.keySet()) { 
                    //每进行一次 for
                    tempSet.clear();
                    //当前这个 key 能够覆盖的地区
                    HashSet<String> areas = broadcasts.get(key);
                    tempSet.addAll(areas);
                    //求出 tempSet 和 allAreas 集合的交集, 交集会赋给 tempSet
                    tempSet.retainAll(allAreas);
                    //如果当前这个集合包含的未覆盖地区的数量，比 maxKey 指向的集合地区还多
                    //就需要重置 maxKey
                    // tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
                    if (tempSet.size() > 0 &&
                            (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) { 
                        maxKey = key;
                    }
                }
                //maxKey != null, 就应该将 maxKey 加入 selects
                if(maxKey != null) { 
                    selects.add(maxKey);
                    //将 maxKey 指向的广播电台覆盖的地区，从 allAreas 去掉
                    allAreas.removeAll(broadcasts.get(maxKey));
                }
            }
            System.out.println("得到的选择结果是" + selects); //[K1,K2,K3,K5]
        }
    }

![在这里插入图片描述][96df226e50a34ee59460405c862d976c.png]

--------------------

**算法应用2——钱币找零**

假设纸币金额为1元、5元、10元、20元、50元、100元

要凑成123元应该尽可能兑换少的纸币

算法思路

*  尽可能从大面值一直往下减即可

Java实现代码：

package com.ai.myproject.atguigu;
    
    /**
     * @author xdragon
     * @Description 贪心算法 | 钱币找零
     * @createTime 2021年08月13日
     */
    public class GreedyAlgorithm2 { 
        public static void main(String[] args) { 
            splitChange(123);
        }
    
        /**
         * 拆分零钱
         *
         * @param money 钱币总金额
         */
        public static void splitChange(int money) { 
            //零钱金额，纸币的种类
            int[] prices = { 100, 50, 20, 10, 5, 1};
            //用于记录每种纸币的数量，下标与prices数组的下标对应
            int[] counts = new int[prices.length];
            //剩下的金额
            int surplus = money;
            if (money > 0) { 
                //如果剩下的金额大于0
                while (surplus > 0) { 
                    //从大金额向小金额进行凑数
                    for (int i = 0; i < prices.length; i++) { 
                        //每张钱币的数量
                        int count = 0;
                        //如果该金额的钱币小于总金额，该钱币数量+1
                        while (surplus - prices[i] >= 0) { 
                            count++;  //该钱币数量+1
                            surplus -= prices[i]; //剩下的金额
                        }
                        counts[i] = count;
                    }
                }
            }
    
            //打印结果
            System.out.println("凑成" + money + "元");
            for (int i = 0; i < prices.length; i++) { 
                if (counts[i] != 0) { 
                    System.out.println("需要" + prices[i] + "元的纸币" + counts[i] + "张");
                }
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 27]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70]: /images/20220829/c216ee5602154a3db3f35029c5f932f4.png
[a8b77a215cce4dd4bfee2271ca0c89d2.png]: /images/20220829/699fb4c0e8f24f518eca8f1f15a60d36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 1]: /images/20220829/7ab2e90173ba4b099480586f8c43d43e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 2]: /images/20220829/eb881ac0fbb04224bbd9e6bf633fb9ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 3]: /images/20220829/76182bc2ebd043debd391b02b3f914a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 4]: /images/20220829/94529a215ea3413689e84125c05c3c0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 5]: /images/20220829/51d679e3480a4c9aba9da31d8cd9a621.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 6]: /images/20220829/7a94b55a9d8a40c3b70d7340d5b67f6f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 7]: /images/20220829/4143c9612a0c41e8937d38449cfcb6df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 8]: /images/20220829/999840125951481b972323df46dfa304.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 9]: /images/20220829/1739a795d88e4743abcdba6fd4c9bad8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 10]: /images/20220829/d46f320404044fd68bf0f17457e24ea4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 11]: /images/20220829/83c379b77b45446a8610be6efbc6c775.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 12]: /images/20220829/d9033cf97d9d460a8dbba213270cbd9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 13]: /images/20220829/db99f60b4d4346d487d1eb7d1c962517.png
[d5a0c6206f1e4ef5920de31e461cf56e.png]: /images/20220829/8658c1cfa08b441ab5d70518903d64c0.png
[c1ab1db83d1d4786980993d56d7db4cb.png]: /images/20220829/a1b40b2e8eac47ae9f28cf0887fd872f.png
[b59f4f7693684569827e81cd6e99cd24.png]: /images/20220829/1ffe8732855e481b99ccdde8a97ef6c6.png
[6f23b1e6f1b3496993a0695cd7e08505.png]: /images/20220829/96c6f930ca3745fba15e0dd8fa7004c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 14]: /images/20220829/448879e5328a46b8b6c9a51e09d789be.png
[f56d1d926df14a959c33f7ee65056d3a.png]: /images/20220829/d2672b2bb6d4407e945c8ace0197dd4d.png
[4718d65e9b474d99885a6161d03561fb.png]: /images/20220829/17a6407646fd4baeaf4d3ac4d5acac83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 15]: /images/20220829/b51a72782fc844dfadae629af21cd950.png
[7347b43710ad4b808b4c4ac9f513a5a7.png]: /images/20220829/2854d5ff4d864715b31838920bde5667.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 16]: /images/20220829/e1db9ce6cd32429f84b0269e7dfe79e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 17]: /images/20220829/987a3c340a7b42c9b778cacee376b870.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 18]: /images/20220829/7c68e337235d4583ae169a7404425653.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 19]: /images/20220829/0c2fd5a4d4094ae8bbfec8210ce2bd2a.png
[cf6ba93352074ca2a06044ae63225942.png]: /images/20220829/921e306c663543bdb0ae94f85312bf13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 20]: /images/20220829/85879019ea95420b96b807fffbc9459d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 21]: /images/20220829/185af7520dcc4ef1a76e011ef4ba8ffc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 22]: /images/20220829/d8ab74cf84e647b0846e161f9e85d905.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 23]: /images/20220829/378365a4ecb14e3e808d849c9af74557.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 24]: /images/20220829/7d37963b873c4d5da6f41cc618b5e10f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 25]: /images/20220829/7ca8d3602c20484bb7e85439f494ae1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 26]: /images/20220829/c36d9968ac564bbbae38a508fb344165.png
[96df226e50a34ee59460405c862d976c.png]: /images/20220829/fcfbb9325218492b83be40da931461bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 27]: /images/20220829/10d67397c42c40f690503bb1b290f4b7.png