关于java:常用十大算法五-贪心算法

罕用十大算法（五）— 贪婪算法

<!– more –>

博客阐明

文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！

介绍

贪心算法 (贪婪算法) 是指在对问题进行求解时，在每一步抉择中都采取最好或者最优 (即最无利) 的抉择，从而心愿可能导致后果是最好或者最优的算法

贪心算法所失去的后果不肯定是最优的后果 (有时候会是最优解)，然而都是绝对近似(靠近) 最优解的后果

汇合笼罩问题

假如存在如下表的须要付费的广播台，以及广播台信号能够笼罩的地区。如何抉择起码的广播台，让所有的地区都能够接管到信号

思路

• 遍历所有的广播电台, 找到一个笼罩了最多未笼罩的地区的电台(此电台可能蕴含一些已笼罩的地区，但没有关系）
• 将这个电台退出到一个汇合中(比方 ArrayList), 想方法把该电台笼罩的地区在下次比拟时去掉。
• 反复第 1 步直到笼罩了全副的地区

代码实现

package com.atguigu.greedy;

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

public class GreedyAlgorithm {public static void main(String[] args) {HashMap<String,HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
        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("大连");
    
        broadcasts.put("K1", hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);
        
        // 所有地区
        HashSet<String> allAreas = new HashSet<String>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
    allAreas.add("天津");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        
        // 电台汇合
        ArrayList<String> selects = new ArrayList<String>();
        
        // 长期汇合
        HashSet<String> tempSet = new HashSet<String>();
        

        String maxKey = null;
        while(allAreas.size() != 0) { 
            maxKey = null;
            for(String key : broadcasts.keySet()) {tempSet.clear();
                HashSet<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                tempSet.retainAll(allAreas);
                if(tempSet.size() > 0 && 
                        (maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){maxKey = key;}
            }
            if(maxKey != null) {selects.add(maxKey);
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println("贪婪算法失去汇合：" + selects);
    }
}

感激

尚硅谷

以及勤奋的本人，集体博客，GitHub