常用算法練習---貪心算法

package commonlyalgorithm.greedalgorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 貪心算法
 *
 * 可以用來求解最少元素覆寫最大面積之類的問題
 * 再次舉例計算選用最少的電台達到要求覆寫的城市全部覆寫的目标
 */
public class GreedAlgorithm {

    public static void main(String[] args) {

        //用來儲存電台資訊的map
        Map<String , HashSet<String>> radioStation = new HashMap<>();

        HashSet<String> nameSet1 = new HashSet<>();
        nameSet1.add("北京");
        nameSet1.add("上海");
        nameSet1.add("天津");

        HashSet<String> nameSet2 = new HashSet<>();
        nameSet2.add("廣州");
        nameSet2.add("北京");
        nameSet2.add("深圳");

        HashSet<String> nameSet3 = new HashSet<>();
        nameSet3.add("成都");
        nameSet3.add("上海");
        nameSet3.add("杭州");

        HashSet<String> nameSet4 = new HashSet<>();
        nameSet4.add("上海");
        nameSet4.add("天津");

        HashSet<String> nameSet5 = new HashSet<>();
        nameSet5.add("杭州");
        nameSet5.add("大連");

        radioStation.put("K1" , nameSet1);
        radioStation.put("K2" , nameSet2);
        radioStation.put("K3" , nameSet3);
        radioStation.put("K4" , nameSet4);
        radioStation.put("K5" , nameSet5);

        //建立儲存所有地區資訊的集合
        HashSet<String> allArea = new HashSet<>();
        allArea.add("北京");
        allArea.add("上海");
        allArea.add("天津");
        allArea.add("廣州");
        allArea.add("深圳");
        allArea.add("成都");
        allArea.add("杭州");
        allArea.add("大連");

        //建立儲存結果的list
        ArrayList<String> selectedList = new ArrayList<>();

        //聲明一個臨時的hash集合用來儲存   周遊過程中的回結果
        HashSet<String> tempSet = new HashSet<>();

        //聲明一個空串用來儲存臨時的最大值
        String maxKey = null;

        //循環求解  每當找到比對的電台後就把地名從集合中删除，直到集合為空，循環結束
        while (allArea.size() != 0){
            //每次大循環前都需要将maxKey置為空
            maxKey = null;
            //循環周遊每一個電台  并将值付給臨時的set集合
            for (String key : radioStation.keySet()) {
                //每次小循環開始前需要将tempSet清空
                tempSet.clear();
                HashSet areas = radioStation.get(key);
                tempSet.addAll(areas);
                //找出臨時集合與全部地區集合的交集
                tempSet.retainAll(allArea);
                //判斷條件并給maxKey指派，經過多次循環後找到符合條件的最大值  此處展現貪心算法的核心思想
                //當符合條件的地區集合不為空且maxKry并未被指派或者目前電台符合條件的值大于上一個符合條件的電台的值時 将其交換
                if(tempSet.size() > 0 && (maxKey == null || tempSet.size() > radioStation.get(maxKey).size())){
                    maxKey =  key;
                }
            }
            //如果maxKey不為空，則将maxKey加入結果集，并将地域集合中maxKey所代表的區域删除
            if(maxKey != null){
                selectedList.add(maxKey);
                allArea.removeAll(radioStation.get(maxKey));
            }
        }

        //循環結束顯示結果   其結果并議定為最優結果，可能為最優結果中的一種
        System.out.println("結果為： " + selectedList);

    }

}