【数据结构与算法之贪心算法】案例

ゝ一纸荒年。 2024-03-25 19:16 109阅读 0赞

#### 【数据结构与算法之贪心算法】案例 ####

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

*   *   *  【数据结构与算法之贪心算法】案例
         *   *   *  1 分薄饼问题
                 *  2 集合覆盖问题

###### 1 分薄饼问题 ######

幼儿园老师给小朋友分饼，每个小朋友最多只能分到一块，对于每一个小朋友i，都有一个需求值gi，即能让小朋友i 满足需求的饼的最小尺寸。

同时每块薄饼j 都有一个尺寸sj，如果sj ≥ gi，就可以将饼j 分给小朋友i。

求解最多能满足几位小朋友。

【输入】\[1,2,3\] \[1,1\]，\[1,2,3\] 代表3个小朋友的需求值，\[1,1\] 表示两块饼的尺寸。

【输出】1

【输入】\[1,2\] \[1,2,3\]，\[1,2\] 代表两个小朋友的需求值，\[1,2,3\] 代表3块饼的尺寸。

【输出】2

贪心算法Java 实现：

import java.util.Arrays;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: SplitTheCake
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 19:29
     */
    
    public class SplitTheCake {
        
    
        public static int getContentedChildren(int g[], int s[]) {
         // g是需求, s是饼
            Arrays.sort(g);
            Arrays.sort(s);
    
            int i = 0;
            int j = 0;
            int count = 0;
    
            while (i <= g.length - 1 && j <= s.length - 1) {
        
                if (g[i] <= s[j]) {
        
                    count++;
                    i++;
                    j++;
                } else {
        
                    j++; // 换更大的饼
                }
            }
    
            return count;
        }
    
        public static void main(String[] args) {
        
    
            int[] g = {
        1, 2}; // 小朋友需求
            int[] s = {
        1, 2, 3}; // 饼
    
            System.out.println(getContentedChildren(g, s));
    
        }
    
    }

运行结果

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

###### 2 集合覆盖问题 ######

假设你办了一个广播节目，要让全美50 个州的听众都能听到。

为此你需要决定在哪些广播台播出这个节目。在每个广播台播出都需要支付费用，所以要在尽可能少的广播台播出。

广播台名单：

<table> 
 <thead> 
  <tr> 
   <th align="center">广播台名称</th> 
   <th align="center">覆盖的州</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">KONE</td> 
   <td align="center">ID、NV、UT</td> 
  </tr> 
  <tr> 
   <td align="center">KTWO</td> 
   <td align="center">WA、ID、MT</td> 
  </tr> 
  <tr> 
   <td align="center">KTHREE</td> 
   <td align="center">OR、NV、CA</td> 
  </tr> 
  <tr> 
   <td align="center">KFOUR</td> 
   <td align="center">NV、UT</td> 
  </tr> 
  <tr> 
   <td align="center">KFIVE</td> 
   <td align="center">CA、ZA</td> 
  </tr> 
 </tbody> 
</table>

如何找到覆盖全美50 个州的最小广播台集合？

【在选择广播时优先选择可覆盖最多未覆盖州的广播台】

举个栗子：

假设现在只有9个州(A B C D E F G H I )，和5个广播台(1,2,3,4,5)

广播台对各个州的覆盖情况：

*  1：A B D E
 *  2：D E G H
 *  3：G H I
 *  4：C F I
 *  5：B C

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

使用贪心策略解决这个问题，步骤如下：

1.  最初，未被覆盖的州：ABCDEFGHI
    
    所以1、2都可以选，这里就选1了，即未被覆盖的州变为CFIGH
    
    ![在这里插入图片描述][f42ec305d8434d7d8ae1c07e04bea5c3.png_pic_center]
2.  选择能够覆盖CFIGH 最多的台，可以通过计算交集的方式来找出这个广播台
    
    得到3、4都可以覆盖3个未覆盖的州，这里就选3了，于是剩下未被覆盖的州变为 CF
    
    ![在这里插入图片描述][dcbf0576837e49279bfcbbd484362547.png_pic_center]
3.  选择能够覆盖CF 最多的广播台，同样用求交集的办法
    
    选出 了4，
    
    ![在这里插入图片描述][e492491eda54493a9ce89d9bc3243356.png_pic_center]
4.  结束

Java代码描述：

import java.util.Arrays;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.LinkedHashMap;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: SetCoveringProblem
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 19:50
     */
    
    public class SetCoveringProblem {
        
    
        public static HashSet<String> getBestBroadCasts(HashSet<String> allStatesSet, LinkedHashMap<String, HashSet<String>> broadCasts) {
        
            HashSet<String> bestbroadCasts = new HashSet<String>();
            String bestBroadCast = "";
    
            //外层循环控制将所有州allStatesSet全部覆盖掉
            while (allStatesSet.size() > 0) {
        
                //内层循环遍历每一个广播站，得到其对应覆盖的州
                //然后计算这些州与剩余未覆盖州的交集
                //选出其中可覆盖最多未覆盖州对应的那个广播站，将其放到bestbroadCasts集合里
                HashSet<String> maxCovered = new HashSet<String>();
                for (HashMap.Entry<String, HashSet<String>> map : broadCasts.entrySet()) {
        
                    HashSet<String> set = map.getValue();  //得到该广播站可覆盖的州的集合
    
                    //计算该广播站可覆盖的州与剩余未覆盖州的交集
    
                    HashSet<String> covered = new HashSet<String>();
                    covered.clear();
                    covered.addAll(set);
                    covered.retainAll(allStatesSet);
    
    
                    //for循环结束后，maxCovered中保存可覆盖的最多未覆盖的州
                    //bestBroadCast中保存对应的广播站的名字
                    if (covered.size() > maxCovered.size()) {
        
    
                        maxCovered = covered;
                        bestBroadCast = map.getKey();
                    }
    
                }
                bestbroadCasts.add(bestBroadCast);  //将bestBroadCast加入bestbroadCasts
                //计算allStatesSet与maxCovered的差集，这样allStatesSet会缩小，将剩下尚未被覆盖的州
                allStatesSet.removeAll(maxCovered);
            }
    
            return bestbroadCasts;
        }
    
        public static void main(String[] args) {
        
            String[] allStates = {
        "mt", "wa", "or", "id", "nv", "ut", "ca", "az"}; //初始化allStates，存放所有需要覆盖的州
            HashSet<String> allStatesSet = new HashSet<String>(Arrays.asList(allStates)); //将字符串数组转换为集合HashSet
            //创建一个HashMap broadCasts，存放广播台和每个广播台可覆盖的州
            LinkedHashMap<String, HashSet<String>> broadCasts = new LinkedHashMap<String, HashSet<String>>();
            //初始化broadCasts
            broadCasts.put("kone", new HashSet<String>(Arrays.asList("id", "nv", "ut")));
            broadCasts.put("ktwo", new HashSet<String>(Arrays.asList("wa", "id", "mt")));
            broadCasts.put("kthree", new HashSet<String>(Arrays.asList("or", "nv", "ca")));
            broadCasts.put("kfour", new HashSet<String>(Arrays.asList("nv", "ut")));
            broadCasts.put("kfive", new HashSet<String>(Arrays.asList("ca", "az")));
            //调用getBestBroadCasts函数得到广播台信息
            System.out.println(getBestBroadCasts(allStatesSet, broadCasts));
        }
    
    }

运行结果

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

[d8886ecbfa8742d29a43d0c31823caaa.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d3dc0a77a167434b850605d4bc8c2e08.png
[8473a05b50bb4c0cb8b5a223c52cc477.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/cefbde0418db41c49049ae30663e8181.png
[f42ec305d8434d7d8ae1c07e04bea5c3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/19567974fb6947a891068d07c5c18673.png
[dcbf0576837e49279bfcbbd484362547.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/88eb50470e8d489eb6af149c3a779ee0.png
[e492491eda54493a9ce89d9bc3243356.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b877fd3de823478eb365fceb1b35fafc.png
[1d08feb187e444999d6a9c1dfd6b8318.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/83bce28d927341c39b6febf5bca27aa4.png