贪婪算法(贪心算法)「建议收藏」

贪婪算法(贪心算法)「建议收藏」贪心算法简介:@anthor:QYX贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。贪心算法每一步必须满足一下条

大家好,又见面了,我是你们的朋友全栈君。

贪心算法简介:

@anthor:QYX

  贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。

  贪心算法每一步必须满足一下条件:

  1、可行的:即它必须满足问题的约束。

  2、局部最优:他是当前步骤中所有可行选择中最佳的局部选择。

  3、不可取消:即选择一旦做出,在算法的后面步骤就不可改变了。

贪心算法的定义:
贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
解题的一般步骤是:
1.建立数学模型来描述问题;
2.把求解的问题分成若干个子问题;
3.对每一子问题求解,得到子问题的局部最优解;
4.把子问题的局部最优解合成原来问题的一个解。
如果大家比较了解动态规划,就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题,把解空间的遍历视作对子问题树的遍历,则以某种形式对树整个的遍历一遍就可以求出最优解,大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪,两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法,我们自底向上构造子问题的解,对每一个子树的根,求出下面每一个叶子的值,并且以其中的最优值作为自身的值,其它的值舍弃。而贪心算法是动态规划方法的一个特例,可以证明每一个子树的根的值不取决于下面叶子的值,而只取决于当前问题的状况。换句话说,不需要知道一个节点所有子树的情况,就可以求出这个节点的值。由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始,选择最优的路,一直走到底就可以了。

使用贪婪算法求解如下问题:
贪婪算法(贪心算法)「建议收藏」

 

 代码:

package com.qyx.Tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GreedyAlgorithm {
    public static void main(String[] args) {
    
        Map<String, HashSet<String>> broadcasts=new HashMap<String,HashSet<String>>();
        //将电台存入map中
        HashSet<String> hashSet=new HashSet<String>();
        hashSet.add("北京");
        hashSet.add("天津");
        hashSet.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", hashSet);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);
        //存放所有的地区
        Set<String> allAreas=new HashSet<String>();
        allAreas.add("北京");
        allAreas.add("天津");
        allAreas.add("大连");
        allAreas.add("成都");
        allAreas.add("广州");
        allAreas.add("上海");
        allAreas.add("杭州");
        allAreas.add("深圳");
        //创建ArrayList,存放选择的电台集合
        List<String> selects=new ArrayList<String>();
        //定义一个临时的集合,在遍历过程中,存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        Set<String> tempSet=new HashSet<String>();
        //定义maxKey,保存在一次遍历过程中,能够覆盖最大未覆盖地区对应的电台的key
        //如果maxKey 不为null,则会加入到 selects
        String maxKey=null;
        while(allAreas.size()!=0)
        {
            //每进行一次while,都需要将maxKey置空,将tempSet清空
            maxKey=null;
            //如果allAreas不为0.则表示还有覆盖到所有地区
            
            //遍历 broadcasts,取出对应的Key
            int size=0;
            for(String key:broadcasts.keySet())
            {
                //当key能覆盖的地区
                tempSet.clear();
                HashSet<String> set=broadcasts.get(key);
                tempSet.addAll(set);
                //取交集,求出tempSet和allAreas的交集,交集会赋给tempSet
                tempSet.retainAll(allAreas);
                //如果tempSet集合包含的未覆盖地区比maxKey还要多,则更新maxKey
                if(tempSet.size()>0&& (maxKey==null||tempSet.size()>size))
                {
                    maxKey=key;
                    size=tempSet.size();
                }        
            }
            //将maxKey加入到selects集合中
            if(maxKey!=null)
            {
                selects.add(maxKey);
                //将maxKey指向的广播电台覆盖的地区,从allAreas去掉
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.print(selects);
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155072.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 163邮箱收不到邮件怎么办苹果手机_163邮箱收不到epic邮件

    163邮箱收不到邮件怎么办苹果手机_163邮箱收不到epic邮件电子邮箱在我们工作生活中占有十分重要的地位。从个人使用个人邮箱,到公司企业使用企业邮箱,这些邮箱使用过程中都存在各种各样的疑问。其中163邮箱收不到邮件就是众多朋友的困扰之一。针对这一现象,今天来为大家分享一下,我们应该如何应对。我们首先要区分清楚163邮箱163邮箱包含两种:属于网易的163.com和属于TOM的163.net163.com邮箱介绍:163.com邮箱是中国早期的电子邮件服…

  • 固态硬盘数据丢失能恢复吗?含泪分享:固态硬盘数据恢复方法

    固态硬盘数据丢失能恢复吗?含泪分享:固态硬盘数据恢复方法固态硬盘数据丢失能恢复吗?有些时候又是数据无缘无故丢失导致我们一头雾水的同时又手足无措。其实不论是固态硬盘,还是什么其他电子设备,数据丢失也是可以恢复的。固态硬盘的话,除非芯片被损坏或烧毁。那么点进来看看恢复的方法吧!…

  • 获取股票历史数据和当前数据的API

    获取股票历史数据和当前数据的API关键字:股票,stock,API,接口1.获取股票当前数据新浪数据接口:http://hq.sinajs.cn/list={code}。{code}替换为股票代码,沪市股票代码加前缀sh,深市股票代码加前缀sz。例如:在浏览器地址栏输入:http://hq.sinajs.cn/list=sh601766,sz000002,得到如下结果:varhq_str_sh601766=”中国中车,10.280,10.210,10.310,10.380,10.160,10.300,10.310,.

  • JavaScript动画基本原理

    JavaScript动画基本原理JavaScript动画基本原理在现在做页面很多时候都会用上动画效果。比如下拉菜单,侧边搜索栏,层的弹出与关闭等等。通常我们实现这些动画效果可以采用JavaScript与CSS3两种方式来实现。本文主要介绍JavaScript动画,CSS3的动画下次在总结。对于JavaScript动画目前有很多的动画插件库,如:Jquery等等.以下就简单介绍以下JavaScript动画的实现原理。1.动

    2022年10月16日
  • pycharm 2021最新永久激活码【在线注册码/序列号/破解码】

    pycharm 2021最新永久激活码【在线注册码/序列号/破解码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • mysql如何获取当前时间_mysql怎么获取当前时间「建议收藏」

    mysql如何获取当前时间_mysql怎么获取当前时间「建议收藏」mysql获取当前时间的方法:可以通过执行【selectnow();】语句来获取当前时间。还可以通过执行【selectcurrent_timestamp,current_timestamp();】语句来获取。获得当前日期+时间(date+time)函数:now()mysql>selectnow();+———————+|now()|+——-…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号