贪心算法(集合覆盖问题)
一、是什么？
首先来看一个集合覆盖问题：
假如存在下面需要付费的广播台，以及广播台信号可以覆盖的地区，如何选择最少的广播台，让所有地区都可以接收到信号？
广播台 | 覆盖地区 |
|---|---|
k1 | 北京、上海、天津 |
k2 | 北京、广州、深圳 |
k3 | 上海、成都、杭州 |
k4 | 上海、天津 |
k5 | 杭州、大连 |
也就是说现在地区总共有8个，即北京、上海、天津、广州、深圳、成都、杭州、大连，如何订购最少的广播台，可以收听到这8个地区的广播。
这个问题就是经典的用贪心算法求解的问题。贪心算法是指在每一步选择中都采取最优的策略，从而希望能够导致结果是最优的一种算法。贪心算法所得到的结果并不一定是最优的解，但都是相对接近最优解的结果。
二、案例：
要解决上面的问题，该怎么做呢？常规的做法如下：
- 列出k1、k2、k3、k4、k5的所有可能组合，总共就有
2^5 = 32中组合。怎么来的？就是5个数不考虑顺序进行排列组合嘛。 - 在这32中组合中挑选一种可以覆盖到8个地区，并且广播台最少的组合，那就是本题的解了。
这样做显然很麻烦，要是有100个广播台，那不是完犊子了。但是可以使用贪心算法，提高效率。贪心算法步骤如下：
- 遍历所有的广播台，找到一个包含了最多当前还未覆盖地区的广播台；
- 将这个广播台存起来，想办法把该广播台覆盖的地区中下次选择时，用别的广播台代替；
- 重复上面的步骤直到覆盖了所有的地区。
如果用上面的案例来说的话，那么步骤就是：
- 遍历广播台，一开始所有地区都还没覆盖，遍历后发现k1、k2、k3都是覆盖了3个地区，选择这三个任何一个都可以，我们按照遍历顺序，选择k1。将k1用一个ArrayList保存起来；
- 把k1覆盖的地区从保存地区的集合中去掉，那么现在就只剩下5个地区没覆盖了；
- 再次遍历广播台的集合，现在剩下5个地区未覆盖，即广州、深圳、成都、杭州、大连。哪个广播台包含最多未覆盖的地区，那就选哪个。现在k2、k3、k5都是包含了两个还未被覆盖的地区。按照遍历顺序，选择k2；
- 再把k2覆盖的地区从保存地区的集合中去掉，那么现在就剩下成都、杭州、大连三个地方未覆盖了；
- 遍历广播台集合，发现k3和k5都可以覆盖两个，按照遍历顺序，选择k3；
- 再把k3覆盖的地区从保存地区的集合中去掉，那么现在就剩下大连未覆盖了；
- 毫无疑问，最后要选择k5，因为只有k5能够覆盖大连。
所以最终的选择结果是k1、k2、k3、k5。
三、代码实现：
将上面的问题用代码实现出来。
public class GreedyDemo {
public static void main(String[] args) {
// 广播电台及其对应覆盖地区用map保存
Map<String, Set<String>> map = new HashMap<>();
Set<String> areaSet1 = new HashSet<>();
areaSet1.add("北京");
areaSet1.add("上海");
areaSet1.add("天津");
Set<String> areaSet2 = new HashSet<>();
areaSet2.add("北京");
areaSet2.add("广州");
areaSet2.add("深圳");
Set<String> areaSet3 = new HashSet<>();
areaSet3.add("上海");
areaSet3.add("成都");
areaSet3.add("杭州");
Set<String> areaSet4 = new HashSet<>();
areaSet4.add("上海");
areaSet4.add("天津");
Set<String> areaSet5 = new HashSet<>();
areaSet5.add("杭州");
areaSet5.add("大连");
map.put("k1", areaSet1);
map.put("k2", areaSet2);
map.put("k3", areaSet3);
map.put("k4", areaSet4);
map.put("k5", areaSet5);
System.out.println(greedy(map));;
}
public static List<String> greedy(Map<String, Set<String>> map){
// 遍历map，拿到所有地区，保存起来
Set<String> allArea = new HashSet<>();
for(String key : map.keySet()) {
allArea.addAll(map.get(key));
}
// 用来保存所选电台的集合
List<String> selected = new ArrayList<>();
Set<String> temp = new HashSet<>();
String selectedKey = null;
while (allArea.size() != 0) {
for (String key : map.keySet()) {
temp.clear();
selectedKey = null;
Set<String> area = map.get(key);
temp.addAll(area);
// 跟allArea求交集
temp.retainAll(allArea);
if (temp.size() > 0 && (selectedKey == null || temp.size() > map.get(selectedKey).size())) {
selectedKey = key;
}
// 找到了当前这一轮选择的广播台
if (selectedKey != null) {
selected.add(selectedKey);
allArea.removeAll(map.get(selectedKey));
}
}
}
return selected;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
