在我們日常生活當中,很多地方都用到了貪心算法的思想,只是我們並未發覺,現在就來說說什麼是貪心算法吧。
什麼是貪心算法?
貪心算法又被稱之為“貪婪算法”。它是指在對問題進行求解時,在每一步的選擇中找到最優解,也稱之為局部最優解。貪心算法並不考慮整體情況。所以貪心算法所得到的結果最終可能並不是最優的結果。
下面來做一個案例,來體會貪心算法。集合覆蓋問題
貪心法解決集合覆蓋問題
問題描述:假設存在下面要付費的廣播電臺,以及廣播信號可以覆蓋的區域。如何選擇最少的廣播電臺,讓所有的地區都可以收到信號
思路:
- 遍歷所有的廣播電臺,找到一個包含了未覆蓋區域最多的電臺,maxValue
- 將這個電臺添加到集合中。在allArea中去掉此電臺覆蓋的區域
- 重複步驟
<code>package com.algorithm.greedy; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; //使用貪心算法解決集合覆蓋的問題 public class greedyAlgorithm { //用來存儲每個廣播電臺分別都對應那些城市 static HashMap> broadcast=new HashMap<>(); //存放電臺覆蓋的區域 static HashSet allAreas=new HashSet(); public static void main(String[] args) { init(); countArea(); select(); } //初始化,將電臺信息加入到braoadcast中 public static void init() { HashSet set1=new HashSet<>(); set1.add("北京"); set1.add("上海"); set1.add("天津"); HashSet set2=new HashSet<>(); set2.add("廣州"); set2.add("北京"); set2.add("深圳"); HashSet set3=new HashSet<>(); set3.add("成都"); set3.add("上海"); set3.add("杭州"); HashSet set4=new HashSet<>(); set4.add("上海"); set4.add("天津"); HashSet set5=new HashSet<>(); set5.add("杭州"); set5.add("大連"); broadcast.put("K1", set1); broadcast.put("K2", set2); broadcast.put("K3", set3); broadcast.put("K4", set4); broadcast.put("K5", set5); } //將電臺覆蓋的區域加入到allArea中 public static void countArea() { for(String key : broadcast.keySet()) { for(String area: broadcast.get(key)) { allAreas.add(area); } } } //選擇電臺 public static void select() { //用來存放選擇了哪些電臺 ArrayList selects=new ArrayList<>(); HashSet temp=new HashSet(); String maxKey=null; //找到當前情況下最優的的那個電臺 //當還有地區沒有被覆蓋掉時 while(allAreas.size()!=0) { maxKey=null; for(String key: broadcast.keySet()) { //將temp置空 temp.clear(); temp.addAll(broadcast.get(key)); //求交集後賦值給temp temp.retainAll(allAreas); if(temp.size()>0&&(maxKey==null||temp.size()>broadcast.get(maxKey).size())) { maxKey=key; } } if(maxKey!=null) { selects.add(maxKey); allAreas.removeAll(broadcast.get(maxKey)); } } System.out.println("得到的選擇結果"+selects); } }/<code>
以上就是貪心算法的講解。在之後,我會發布一些相關的使用貪心算法求解的算法題。歡迎大家評論討論。