|
「一、是什么？」 首先来看一个「集合覆盖问题」： 假如存在下面需要付费的广播台，以及广播台信号可以覆盖的地区，如何选择最少的广播台，让所有地区都可以接收到信号？ | 广播台 | 覆盖地区 |
|---|
| 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;
}
}
|
