贪婪算法-电塔覆盖城市问题

本文主要是介绍贪婪算法-电塔覆盖城市问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

package ten_algorithm.greedy;import com.sun.deploy.panel.ITreeNode;
import sun.plugin2.message.GetAppletMessage;import java.util.*;/*** Author:jinpma* Date :2019/12/28*/
public class BroadCastDemo
{public static void main(String[] args){//1.定义(Map集合(电台-地区)、List集合(电台))Map<String, HashSet<String>> map = new HashMap<>();HashSet<String> K1Areas = new HashSet<>();HashSet<String> K2Areas = new HashSet<>();HashSet<String> K3Areas = new HashSet<>();HashSet<String> K4Areas = new HashSet<>();HashSet<String> K5Areas = new HashSet<>();K1Areas.add("北京");K1Areas.add("上海");K1Areas.add("天津");map.put("K1", K1Areas);K2Areas.add("北京");K2Areas.add("广州");K2Areas.add("深圳");map.put("K2", K2Areas);K3Areas.add("成都");K3Areas.add("上海");K3Areas.add("杭州");map.put("K3", K3Areas);K4Areas.add("天津");K4Areas.add("上海");map.put("K4", K4Areas);K5Areas.add("杭州");K5Areas.add("大连");map.put("K5", K5Areas);List<String> allAreasList = new ArrayList<>();for (Map.Entry<String, HashSet<String>> item : map.entrySet()){HashSet<String> KiAreas = item.getValue();allAreasList.addAll(KiAreas);}//System.out.println(allAreasList);//[上海(0), 天津(1), 北京(2), 广州(3), 北京(4), 深圳(5), 成都(6), 上海(j = 7要被删除), 杭州, 上海, 天津, 大连, 杭州]//接下来的for循环完全可以用HashSet存储，因为HashSet存储的元素不重复for (int i = 0; i < allAreasList.size(); i++){for (int j = i + 1; j < allAreasList.size(); j++){if (allAreasList.get(i) == allAreasList.get(j)){allAreasList.remove(j);//[上海(0), 天津(1), 北京(2), 广州(3), 北京(4), 深圳(5), 成都(6), (上海(7)被删除了), 杭州(7), 上海(8要被删除), 天津, 大连, 杭州]j --;//!!!!!!!因为后面j++会往后两个元素了[上海(0), 天津(1), 北京(2), 广州(3), 北京(4), 深圳(5), 成都(6), 杭州(7), 上海(被删除), 天津(8), 大连, 杭州]}}}//[上海, 天津, 北京, 广州, 深圳, 成都, 杭州, 大连]List<String> resList = BroadCastDemo.findK(map, allAreasList);System.out.println(resList);}public static List<String> findK(Map<String,HashSet<String>> map,List<String> allAreasList){List<String> kiList = new ArrayList<>();String maxKey = null;//while (allAreasList.size() > 0){maxKey = null;//第一趟寻找maxKey=K1,下一趟开始时为空//单趟，寻找最大指针maxKeyfor (Map.Entry<String, HashSet<String>> item : map.entrySet()){HashSet<String> kiAreas = item.getValue();//获取Ki对应的所有地区kiAreas.retainAll(allAreasList);//集合list1与集合list2重合的部分，赋值给list1(k1Areas.size()==3)if (kiAreas.size() > 0 && (maxKey == null || kiAreas.size() > map.get(maxKey).size())){maxKey = item.getKey();}}//找到了if (maxKey != null){kiList.add(maxKey);allAreasList.removeAll(map.get(maxKey));//将k1的城市全部移除}}return kiList;}}