Java贪心算法实例分析(java,开发技术)

贪心算法

贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果.

贪心算法的优缺点:

• 优点: 贪心算法的代码十分简单

• 缺点: 很难确定一个问题是否可以用贪心算法解决

电台覆盖问题

假设存在以下的广播台, 以及广播台可以覆盖的地区:

广播台覆盖地区K1北京, 上海, 天津K2北京, 广州, 深圳K3上海, 杭州, 成都K4上海, 天津K5杭州, 大连

贪心算法的核心思想:

• 把所有需要覆盖的地区取集合

• 从电台中取覆盖集合中地区最多的一个

• 集合中去除已覆盖地区, 继续匹配

代码实现

importjava.util.ArrayList;importjava.util.Arrays;importjava.util.HashMap;importjava.util.HashSet;publicclass贪心算法{//集合,存放广播台staticHashMap<String,HashSet<String>>broadcasts=newHashMap<>();//集合,存放地区staticHashSet<String>areas=newHashSet<String>();//贪心算法publicstaticArrayList<String>Greedy(){//创建数组存放结果ArrayList<String>selects=newArrayList<>();//循环直至地区都覆盖while(areas.size()!=0){//存放交集最大的广播台StringmaxKey=null;//存放交集最大的值intmaxKeySize=0;//遍历每个剩余电台for(Stringkey:broadcasts.keySet()){//取出交集个数intcurrSize=getRetainSize(key);//替换当前最大if(currSize>0&&currSize>maxKeySize){maxKey=key;maxKeySize=currSize;}}//添加广播台到结果selects.add(maxKey);//移除广播台areas.removeAll(broadcasts.get(maxKey));}returnselects;}//剩余数量publicstaticintgetRetainSize(Stringkey){//如果为空返回0if(key==null)return0;//存放key对应的地区集合HashSet<String>tempSet=newHashSet<>();//取key对应的地区tempSet.addAll(broadcasts.get(key));//取交集tempSet.retainAll(areas);returntempSet.size();}publicstaticvoidmain(String[]args){//|K1|北京,上海,天津|//|K2|北京,广州,深圳|//|K3|上海,杭州,成都|//|K4|上海,天津|//|K5|杭州,大连|//创建广播台HashSet<String>K1=newHashSet<>(Arrays.asList("北京","上海","天津"));HashSet<String>K2=newHashSet<>(Arrays.asList("北京","广州","深圳"));HashSet<String>K3=newHashSet<>(Arrays.asList("上海","杭州","成都"));HashSet<String>K4=newHashSet<>(Arrays.asList("上海","天津"));HashSet<String>K5=newHashSet<>(Arrays.asList("杭州","大连"));//加入mapbroadcasts.put("K1",K1);broadcasts.put("K2",K2);broadcasts.put("K3",K3);broadcasts.put("K4",K4);broadcasts.put("K5",K5);areas.addAll(K1);areas.addAll(K2);areas.addAll(K3);areas.addAll(K4);areas.addAll(K5);//调试输出System.out.println(broadcasts);System.out.println(areas);ArrayList<String>result=Greedy();System.out.println(result);}}

 </div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">