首页 > 编程语言 >贪心算法

贪心算法

时间:2022-10-01 10:34:12浏览次数:51  
标签:allAreas 覆盖 HashSet add maxKey 算法 broadcasts 贪心

  • 应用实例
假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台,让所有的地区都可以接收到信号

贪心算法_应用实例

  • 思路分析
目前并没有算法可以快速计算得到准备的值, 使用贪婪算法,则可以得到非常接近的解,并且效率高。选择策略上,因为需要覆盖全部地区的最小集合:
遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区,但没有关系)
将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
重复第1步直到覆盖了全部的地区
  • 先将所有地区放到1个集合中,遍历第1次,发现K1覆盖了3个地区
  • 贪心算法_贪婪算法_02

  • maxKey指向K1广播,将K1放到selects集合中
  • 贪心算法_贪婪算法_03

  • 同时将allAreas集合中的K1对应的地区删除,key再遍历第2次时,K1覆盖0个地区,K2覆盖2个地区
  • 贪心算法_应用实例_04

  • 依次类推
  • 代码实现
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 = 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);
//如果当前这个集合包含的未覆盖地区的数量,比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);//[K1,K2,K3,K5]
}

}



标签:allAreas,覆盖,HashSet,add,maxKey,算法,broadcasts,贪心
From: https://blog.51cto.com/chniny/5728145

相关文章

  • 暴力匹配算法、KMP算法
    应用实例暴力匹配算法代码实现publicclassViolenceMatch{publicstaticvoidmain(String[]args){//测试暴力匹配算法Stringstr1="硅硅谷尚硅谷你尚硅......
  • 动态规划算法
    应用实例有一个背包,容量为4磅,现在将如下商品装入背包,要求装入的背包的总价值最大,并且重量不超出,且物品不能重复#当前为01背包#如果为完全背包则放入物品可重复简介思路分......
  • 非递归的方式实现二分查找算法
    简介二分查找法的运行时间为对数时间O(㏒₂n),即查找到需要的目标位置最多只需要㏒₂n步,假设从[0,99]的队列(100个数,即n=100)中寻到目标数30,则需要查找步数为㏒₂100,即最......
  • React面试:谈谈虚拟DOM,Diff算法与Key机制
    1.虚拟dom原生的JSDOM操作非常消耗性能,而React把真实原生JSDOM转换成了JavaScript对象。这就是虚拟Dom(VirtualDom)每次数据更新后,重新计算虚拟Dom,并和上一次生成的虚拟......
  • LeetCode 无重复字符的最长子串算法题解 All In One
    LeetCode无重复字符的最长子串算法题解AllInOnejs/ts实现无重复字符的最长子串无重复字符的最长子串原理图解滑动窗口"usestrict";/****@authorx......
  • Python基本算法实现及总结归纳
    @目录冒泡排序快速排序插入排序选择排序希尔排序归并排序各个算法的时间复杂度附:二分法冒泡排序这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(......
  • 传统优化方法:枚举法、启发式算法和搜索算法
    1.枚举法枚举出可行解集合内的所有可行解,以求出精确最优解。对于连续函数,该方法要求先对其进行离散化处理,这样就可能因离散处理而永远达不到最优解。当枚举空间比较大时......
  • PTA 21级数据结构与算法实验5—树和二叉树
    目录7-1还原二叉树7-2朋友圈7-3修理牧场7-4玩转二叉树7-5根据后序和中序遍历输出先序遍历7-6完全二叉树的层序遍历7-7列出叶结点7-8部落7-9建立与遍历二叉树7-10......
  • 基于微粒群算法的0-1背包问题求解
    importrandomimportmathimportmatplotlib.pyplotaspltimportnumpyasnpimporttimedefinit(b_=700,xSize_=200,iteration_=1000,c1_=0.5,c2_=0.5,w_=0.8):......
  • Raft 共识算法
    转载请注明出处:https://www.cnblogs.com/morningli/p/16745294.htmlraft是一种管理复制日志的算法,raft可以分解成三个相对独立的子问题:选主(Leaderelection):原有的lead......