Java使用贪心算法解决电台覆盖问题(示例详解)

/**

  * 贪心算法实现集合覆盖

  */

public class Demo {

     public static void main(String[] args) {

         // 创建电台和地区集合

         HashMap<String, HashSet<String>> broadcasts = new HashMap<>();

         // 创建各个电台

         HashSet<String> k1 = new HashSet<>();

         k1.add( "北京" );

         k1.add( "上海" );

         k1.add( "天津" );

         HashSet<String> k2 = new HashSet<>();

         k2.add( "广州" );

         k2.add( "北京" );

         k2.add( "深圳" );

         HashSet<String> k3 = new HashSet<>();

         k3.add( "成都" );

         k3.add( "上海" );

         k3.add( "杭州" );

         HashSet<String> k4 = new HashSet<>();

         k4.add( "上海" );

         k4.add( "天津" );

         HashSet<String> k5 = new HashSet<>();

         k5.add( "杭州" );

         k5.add( "大连" );

         // 加入各个电台

         broadcasts.put( "k1" , k1);

         broadcasts.put( "k2" , k2);

         broadcasts.put( "k3" , k3);

         broadcasts.put( "k4" , k4);

         broadcasts.put( "k5" , k5);

         // 建立各个地区的集合

         HashSet<String> allAreas = new HashSet<>();

         for (Map.Entry<String, HashSet<String>> entry : broadcasts.entrySet()) {

             HashSet<String> value = entry.getValue();

             allAreas.addAll(value);

         }

         // 创建选择的电台的集合

         ArrayList<String> broadSelect = new ArrayList<>();

         // 定义一个临时的集合

         HashSet<String> tempSet = new HashSet<>();

         // 定义一个指针，用于指向当前最优

         String maxKey = null ;

         while (allAreas.size() > 0 ) {

             // 重置置空

             maxKey = null ;

             // 遍历

             for (String key : broadcasts.keySet()) {

                 // 重置置空

                 tempSet.clear();

                 HashSet<String> value = broadcasts.get(key);

                 tempSet.addAll(value);

                 // 求出temp和allAreas的交集

                 tempSet.retainAll(allAreas);

                 // 如果当前选择有覆盖地区

                 if (tempSet.size() > 0 &&

                         // 此时，如果maxKey还没有指向就指向

                         (maxKey == null ||

                                 // 如果maxKey已经有指向就比较谁最优解

                                 (tempSet.size() > (broadcasts.get(maxKey).size())))) {

                     maxKey = key;

                 }

             }

             if (maxKey != null ) {

                 // 将maxKey加入

                 broadSelect.add(maxKey);

                 // 并将allAreas去掉maxKey能覆盖的地区

                 allAreas.removeAll(broadcasts.get(maxKey));

         // 打印结果

         System.out.println(broadSelect);

     }

}

package azhong.greedy_algo;

import java.util.*;

/**

  * 贪心算法

  * 在对问题求解时，在每一步都选择最好的选择，从而希望得到最好的结果。

  */

public class GreedyAlgoDemo {

     public static void main(String[] args) {

         //每个电台覆盖的区域

         Map<String,HashSet<String>> allStations = initRadioStation();

         //需要覆盖的所有区域

         HashSet<String> allAreas = getAllAreas(allStations);

         //存放选择的电台

         List<String> selectedStations = new ArrayList<>();

         while (allAreas.size()> 0 ) {

             //遍历所有广播台，找到了个覆盖了最多未覆盖的地区的电台

             int maxIndex= 0 ;

             String maxK= null ;

             HashSet<String> areaInMaxK= null ;

             for (Map.Entry<String, HashSet<String>> entry : allStations.entrySet()) {

                 final String k = entry.getKey();

                 HashSet<String> values = entry.getValue();

                 //当前电台在所有区域覆盖的个数

                 int c = testIntersectionOfSet(values, allAreas);

                 System.out.println(k + " 在所有区域覆盖的个数: " + c);

                 if (c>maxIndex){

                     maxIndex=c;

                     maxK=k;

                     areaInMaxK=values;

                 }

             }

             if (maxK!= null ){

                 //选择最大覆盖数k1加入到选择的电台{k1}，

                 selectedStations.add(maxK);

                 //将k1（北京、上海、天津）从所覆盖的区域从所有区域中移除，所有区域更新为：{山东、深圳、成都、杭州、武汉};

                 allAreas.removeAll(areaInMaxK);

                 //重置，进入下一次循环

                 maxIndex= 0 ;

                 maxK= null ;

                 areaInMaxK= null ;

                 System.out.println( "****************************" );

         }

         System.out.println(selectedStations);

     }

     /**

      * 测试：求两个集合的交集

      * A{北京、上海、天津}

      * B{北京、上海、天津、山东、深圳、成都、杭州、武汉}

      * A.retainAll(B); 得到A{北京、上海、天津} 个数为3

      */

     private static int testIntersectionOfSet(HashSet A,HashSet B){

         //将存在于集合A中但不存在于集合B中的元素移除。

         A.retainAll(B);

         return A.size();

      * 初始化电台

      * k1广播台覆盖的区域有：北京、上海、天津

      * k2广播台覆盖的区域有：北京、山东、深圳

      * k3广播台覆盖的区域有：成都、上海、杭州

      * k4广播台覆盖的区域有：上海、天津

      * k5广播台覆盖的区域有：杭州、武汉

      * @return Map<String,HashSet<String>>类型电台集合

     private static Map<String,HashSet<String>> initRadioStation(){

         Map<String,HashSet<String>> allStations = new HashMap<String,HashSet<String>>();

         HashSet<String> k1 = new HashSet<>();

         k1.add( "北京" );

         k1.add( "上海" );

         k1.add( "天津" );

         HashSet<String> k2 = new HashSet<>();

         k2.add( "北京" );

         k2.add( "山东" );

         k2.add( "深圳" );

         HashSet<String> k3 = new HashSet<>();

         k3.add( "成都" );

         k3.add( "上海" );

         k3.add( "杭州" );

         HashSet<String> k4 = new HashSet<>();

         k4.add( "上海" );

         k4.add( "天津" );

         HashSet<String> k5 = new HashSet<>();

         k5.add( "杭州" );

         k5.add( "武汉" );

         allStations.put( "k1" ,k1);

         allStations.put( "k2" ,k2);

         allStations.put( "k3" ,k3);

         allStations.put( "k4" ,k4);

         allStations.put( "k5" ,k5);

         return allStations;

     private static HashSet<String> getAllAreas(Map<String,HashSet<String>> allStations){

         HashSet<String> allAreas = new HashSet<>();

         Collection<HashSet<String>> stations = allStations.values();

         for (HashSet<String> station:stations){

             Iterator<String> areas = station.iterator();

             //操泥玛，写成了if

             while (areas.hasNext()){

                 allAreas.add(areas.next());

         return allAreas;

}