【算法】贪心算法

应用场景——集合覆盖问题

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

贪心算法先容

1.贪心算法是指在对问题举行求解时，在每一步选择中都采取最好大概最优的选择
2.贪心算法得到的结果不肯定是最优的结果，但是都是相对近似最优解的结果
思路分析

使用贪心算法的服从非常高，选择策略上，由于必要覆盖全部小区的所有集合：
1.遍历所有的广播电台，找到一个覆盖了最多未覆盖地区的电台（此电台可能包含一些已覆盖的地区，但没有关系）
2.将这个电台参加到一个集合中（比如 ArrayList），想办法把该电台覆盖的地区在下次比较时去掉
3.重复第 1 步直到覆盖了全部的地区
用代码实现集合覆盖问题

1. public class GreedyAlgorithm {
2.     public static void main(String[] args) {
3.         //创建广播电台，放入到 Map
4.         HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
5.         //将各个电台放入到 broadcasts
6.         HashSet<String> hashSet1 = new HashSet<>();
7.         hashSet1.add("北京");
8.         hashSet1.add("上海");
9.         hashSet1.add("天津");
11.         HashSet<String> hashSet2 = new HashSet<>();
12.         hashSet2.add("广州");
13.         hashSet2.add("北京");
14.         hashSet2.add("深圳");
16.         HashSet<String> hashSet3 = new HashSet<>();
17.         hashSet3.add("成都");
18.         hashSet3.add("上海");
19.         hashSet3.add("杭州");
21.         HashSet<String> hashSet4 = new HashSet<>();
22.         hashSet4.add("上海");
23.         hashSet4.add("天津");
25.         HashSet<String> hashSet5 = new HashSet<>();
26.         hashSet5.add("杭州");
27.         hashSet5.add("大连");
29.         //加入到 Map
30.         broadcasts.put("k1", hashSet1);
31.         broadcasts.put("k2", hashSet2);
32.         broadcasts.put("k3", hashSet3);
33.         broadcasts.put("k4", hashSet4);
34.         broadcasts.put("k5", hashSet5);
36.         //allAreas 存放所有地区
37.         HashSet<String> allAreas = new HashSet<>();
38.         allAreas.add("北京");
39.         allAreas.add("上海");
40.         allAreas.add("天津");
41.         allAreas.add("广州");
42.         allAreas.add("深圳");
43.         allAreas.add("成都");
44.         allAreas.add("杭州");
45.         allAreas.add("大连");
47.         //创建 ArrayList，存放选择的电台集合
48.         ArrayList<String> selects = new ArrayList<>();
50.         //定义一个临时的集合，在遍历过程中，存放遍历过程中电台覆盖的地区和当前还没有覆盖的地区的交集
51.         HashSet<String> tempSet = new HashSet<>();
53.         /*
54.         定义一个 maxKey，保存在一次遍历过程中，能够覆盖最大未覆盖地区的电台的 key
55.         如果 maxKey 不为 null，则会加入到 selects
56.          */
57.         String maxKey = null;
58.         while (allAreas.size() != 0) {  //如果 allAreas 不为 0，则表示还没有覆盖到所有的地区
59.             //每进行一次 while，需要
60.             maxKey = null;
61.             //遍历 broadcasts，取出对应 key
62.             for (String  key : broadcasts.keySet()) {
63.                 //每进行一次 for
64.                 tempSet.clear();
65.                 //当前这个 key 能够覆盖的地区
66.                 HashSet<String> areas = broadcasts.get(key);
67.                 tempSet.addAll(areas);
68.                 //求出 tempSet 和 allAreas 集合的交集，交集会赋给 tempSet
69.                 tempSet.retainAll(allAreas);
70.                 //如果当前这个集合包含的未覆盖地区的数量，比 maxKey 指向的集合地区还多
71.                 //就需要重置 maxKey
72.                 // (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size()) 体现出贪心的特点
73.                 if (tempSet.size() > 0 &&
74.                         (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())
75.                 ) {
76.                     maxKey = key;
77.                 }
78.             }
80.             //maxKey != null，就应该将 maxKey 加入 selects
81.             if (maxKey != null) {
82.                 selects.add(maxKey);
83.                 //将 maxKey 指向的广播电台覆盖的地区，从 allAreas 去掉
84.                 allAreas.removeAll(broadcasts.get(maxKey));
85.             }
87.         }
88.         System.out.println("得到的选择结果是" + selects);
89.     }
90. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。