java貪心算法初學感悟圖解及示例分享
算法簡介
1)貪心算法是指在對問題進行求解時,在每一步選擇中都采取最好或者最優(即最有利)的選擇,從而希望能夠導致是最好或者最優的算法
2)貪心算法所得到的結果不一定是最優的結果(有時候會是最優解),但是都是相對近似(接近)最優解的結果。
應用場景 –> 集合覆蓋
public class GreedyAlgorithm { public static void main(String[] args) { // 創建廣播電臺,放入到Map HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>(); // 將各個電臺放入到broadcasts HashSet<String> hashSet1 = new HashSet<String>(); hashSet1.add("北京"); hashSet1.add("上海"); hashSet1.add("天津"); HashSet<String> hashSet2 = new HashSet<String>(); hashSet2.add("廣州"); hashSet2.add("上海"); hashSet2.add("天津"); HashSet<String> hashSet3 = new HashSet<String>(); hashSet3.add("成都"); hashSet3.add("上海"); hashSet3.add("杭州"); HashSet<String> hashSet4 = new HashSet<String>(); hashSet4.add("上海"); hashSet4.add("天津"); HashSet<String> hashSet5 = new HashSet<String>(); hashSet5.add("杭州"); hashSet5.add("大連"); // 加入到map broadcasts.put("K1", hashSet1); broadcasts.put("K2", hashSet2); broadcasts.put("K3", hashSet3); broadcasts.put("K4", hashSet4); broadcasts.put("K5", hashSet5); // allAreas,存放所有的地區 HashSet<String> allAreas = new HashSet<String>(); allAreas.add("北京"); allAreas.add("上海"); allAreas.add("天津"); allAreas.add("廣州"); allAreas.add("深圳"); allAreas.add("成都"); allAreas.add("杭州"); allAreas.add("大連"); // 創建ArrayList,存放選擇的電臺集合 ArrayList<String> selects = new ArrayList<String>(); // 定義一個臨時的集合,在遍歷的過程中,存放遍歷過程中的電臺覆蓋的地區和當前還沒有覆蓋的地區的交集 HashSet<String> tempSet = new HashSet<String>(); // 定義一個maxKey,保存在一次遍歷過程中,能夠覆蓋最多未覆蓋的地區對應的電臺的key // 如果maxKey不為null,則會加入到selects String maxKey = null; while (allAreas.size() != 0) {// 如果allAreas不為0,則表示還沒有覆蓋到所有的地區 // 每進行一次while,需要將maxKey置空 maxKey = null; // 遍歷broadcasts,取出對應key for (String key : broadcasts.keySet()) { // 每進行一次for tempSet.clear(); // 當前這個key能夠覆蓋的地區 HashSet<String> areas = broadcasts.get(key); tempSet.addAll(areas); // 求出tempSet 和 allAreas集合的交集,交集會賦給tempSet tempSet.retainAll(allAreas);// retainAll方法的作用就是求交集 // 如果當前這個集合包含的未覆蓋地區的數量,比maxKey指向的集合地區還多 // 就需要重置maxKey // tempSet.size() > broadcasts.get(maxKey).size()) 體現出貪心算法的特點,每次都選擇最優的 if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) { maxKey = key; } } // maxKey != null,就應該將maxKey加入selects if (maxKey != null) { selects.add(maxKey); // 將maxKey指向的廣播電臺覆蓋的地區,從allAreas去掉 allAreas.removeAll(broadcasts.get(maxKey)); } } System.out.println("得到的選擇結果是" + selects); } }
以上就是java貪心算法初學感悟圖解及示例分享的詳細內容,更多關於java貪心算法的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- Java 數據結構與算法系列精講之貪心算法
- Java 深入淺出掌握Map集合之雙列集合
- 一篇文章帶你入門java集合
- Java HashSet添加 遍歷元素源碼分析
- java 取交集方法retainAll的實現