网站制作的方法,网络推广专员的岗位职责是,文化网站源码,wordpress 手机 插件贪心算法Java实现
贪心算法介绍 贪心算法#xff08;贪婪算法#xff09;是一个遵循启发式解决问题的算法范式#xff0c;核心思想是通过在每一步的选择中都选用当前步骤下最优的选择#xff0c;期望结果是最优的算法。贪心算法得到的结果不一定是最优结果#xff0c;但是…贪心算法Java实现
贪心算法介绍 贪心算法贪婪算法是一个遵循启发式解决问题的算法范式核心思想是通过在每一步的选择中都选用当前步骤下最优的选择期望结果是最优的算法。贪心算法得到的结果不一定是最优结果但是都是相对接近最优解的结果。 步骤
建立问题的数学模型并构建一个备选答案区把待求解的问题分成多个子问题使用一个选择函数对每个子问题求得最优解并判断是否可以用于整个问题把所有子问题的最优解合成一个整个问题的解。
应用场景 贪心算法可以用来求最小生成树、哈夫曼编码、集合覆盖问题等。 使用实例
假设存在下标中的需要付费的广播台以及广播台信号可以覆盖的地区这样选择最少的广播台让所有地区都可以接收到信息。
广播台覆盖地区K1北京上海天津K2广州北京深圳K3成都上海杭州K4上海天津K5杭州大连
解决方案 使用穷举列出每个可能的广播台的集合假设总有有n个广播台则广播台组合总共有2n-1个。 使用贪心算法获取近似解选择策略上需要选择覆盖所有地区的最小集合步骤如下。 遍历所有广播台找到一个覆盖了最多还没有被覆盖地区的电台这个电台可能包含已经覆盖了地区可以忽略把这个电台放入到一个集合中在下次比较时去掉该电台覆盖的地区重复前两个步骤直到覆盖了全部地区。
参考代码
import java.util.*;public class Greedy {//创建广播台MapString, HashSetString broadcasts new HashMap();//添加各个电台HashSetString set1 new HashSet(Arrays.asList(北京, 上海, 天津));HashSetString set2 new HashSet(Arrays.asList(广州, 北京, 深圳));HashSetString set3 new HashSet(Arrays.asList(成都, 上海, 杭州));HashSetString set4 new HashSet(Arrays.asList(上海, 天津));HashSetString set5 new HashSet(Arrays.asList(杭州, 大连));broadcasts.put(K1, set1);broadcasts.put(K2, set2);broadcasts.put(K3, set3);broadcasts.put(K4, set4);broadcasts.put(K5, set5);//存放所有地区HashSetString allAreas new HashSet(Arrays.asList(北京, 上海, 天津, 广州 深圳, 成都, 杭州, 大连));//存放选择的电台ListString selects new ArrayList();//定义一个临时的集合存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集HashSetString tempSet new HashSet();//定义maxKey保存在一次遍历过程中能够覆盖最大未覆盖地区对应的电台的keyString maxKey null;//如果allAreas不为0,就说明还有地区没有被覆盖while(allAreas.size() ! 0) {//每次清理maxKey和tempSetmaxKey null;for (String key:broadcasts.keySet()) {tempSet.clear();//当前Key能够覆盖的地区HashSetString areas broadcasts.get(key);tempSet.addAll(areas);//求出tempSet和allAreas集合的交集重新赋值给tempSettempSet.retainAll(allAreas);//如果当前集合包含的未覆盖地区的数量比maxKey指向的集合地区还多需要重新修改maxKeyif (tempSet.size() 0 (maxKey null || tempSet.size() broadcasts.get(maxKey).size())) {maxKey key;}}//如果maxKey不为空就添加到selects并将maxKey的电台从需要覆盖的电台中移除if (maxKey ! null) {selects.add(maxKey);allAreas.removeAll(broadcasts.get(maxKey));}}System.out.println(得到的选择结果是 selects);
}
