18. 算法之贪心算法

这篇具有很好参考价值的文章主要介绍了18. 算法之贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

贪心算法(greedy algorithm,又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。下面,我们详细介绍。

1. 概念

贪婪算法(Greedy)的定义:是一种在每一步选中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法当下做局部最优判断,不能回退(能回退的是回溯,最优+回退是动态规划),回溯和动态规划后面会讲到。

由于贪心算法的高效性以及所求得答案比较接近最优结果,贪心算法可以作为辅助算法或解决一些要求,结果不特别精确的问题。注意:当下是最优的,并不一定全局是最优的。

举例如下

  1. 有硬币分值为10、9、4若干枚,问如果组成分值18,最少需要多少枚硬币?
    采用贪心算法,选择当下硬币分值最大的:10
    18-10=8
    8/4=2
    即:1个10、2个4,共需要3枚硬币
    实际上我们知道,选择分值为9的硬币,2枚就够了
    18/9=2

  2. 如果改成有硬币分值为10、5、1若干枚,问如果组成分值16,最少需要多少枚硬币?
    采用贪心算法,选择当下硬币分值最大的:10
    16-10=6
    6-5=1
    即:1个10,1个5,1个1 ,共需要3枚硬币,即为最优解
    由此可以看出贪心算法适合于一些特殊的情况,如果能用一定是最优解。

2. 经典问题

背包问题是算法的经典问题,分为部分背包和0-1背包,主要区别如下:
部分背包:某件物品是一堆,可以带走其一部分
0-1背包:对于某件物品,要么被带走(选择了它),要么不被带走(没有选择它),不存在只带走一部分的情况。

部分背包问题可以用贪心算法求解,且能够得到最优解。

假设一共有N件物品,第 i 件物品的价值为 Vi ,重量为Wi,一个小偷有一个最多只能装下重量为W的背包,他希望带走的物品越有价值越好,可以带走某件物品的一部分,请问:他应该选择哪些物品?

假设背包可容纳50Kg的重量,物品信息如下表:

物品 重量(kg) 价值(元) 单位重量的价值(元/kg)
A 10 60 6
B 20 100 5
C 30 120 4

贪心算法的关键是贪心策略的选择将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品。按照我们的贪心策略,单位重量的价值排序: 物品A > 物品B > 物品C
因此,我们尽可能地多拿物品A,直到将物品1拿完之后,才去拿物品B,然后是物品C 可以只拿一部分…

2.2 代码实现

2.2.1 定义商品类

package org.wanlong.algorithm;

/**
 * @author wanlong
 * @version 1.0
 * @description:
 * @date 2023/6/16 14:21
 */
public class Goods {
    String name;
    double weight;
    double price;
    double val;
    public Goods(String name,double weight, double price) {
        this.name=name;
        this.weight = weight;
        this.price = price;
        val=price/weight;
    }
}

2.2.2 贪心算法实现

package org.wanlong.algorithm;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;

/**
 * @author wanlong
 * @version 1.0
 * @description: 贪心算法
 * @date 2023/6/16 14:20
 */
public class Greedy {

    double bag;

    public void take(Goods[] goodslist) {
        // 对物品按照价值排序从高到低
        Goods[] goodslist2 = sort(goodslist);
        double sum_w = 0;
        //取出价值最高的
        for (int i = 0; i < goodslist2.length; i++) {
            sum_w += goodslist2[i].weight;
            if (sum_w <= bag) {
                System.out.println(goodslist2[i].name + "取" + goodslist2[i].weight + "kg");
            } else {
                System.out.println(goodslist2[i].name + "取" + (bag - (sum_w - goodslist2[i].weight)) + "kg");
                return;
            }
        }
    }


    // 按物品的每kg价值排序 由高到低 price/weight
    private Goods[] sort(Goods[] goodslist) {
        Arrays.sort(goodslist, 0, goodslist.length , new Comparator<Goods>() {
            @Override
            public int compare(Goods o1, Goods o2) {
                double i = o2.val - o1.val;
                if (i > 0) {
                    return 1;
                } else if (i == 0) {
                    return 0;
                } else {
                    return -1;
                }
            }
        });
        return goodslist;
    }

    public static void main(String[] args) {
        Greedy bd = new Greedy();
        Goods goods1 = new Goods("A", 10, 60);
        Goods goods2 = new Goods("B", 20, 100);
        Goods goods3 = new Goods("C", 30, 120);

        Goods[] goodslist = {goods1, goods3, goods2};
        bd.bag = 50;
        bd.take(goodslist);
    }

}

3. 时间复杂度

在不考虑排序的前提下,贪心算法只需要一次循环,所以时间复杂度是O(n)

4. 优缺点

优点:性能高,能用贪心算法解决的往往是最优解
缺点:在实际情况下能用的不多,用贪心算法解的往往不是最好的

5. 适用场景

针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。
每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据(局部最优而全局最优)
大部分能用贪心算法解决的问题,贪心算法的正确性都是显而易见的,也不需要严格的数学推导证明,在实际情况下,用贪心算法解决问题的思路,并不总能给出最优解文章来源地址https://www.toymoban.com/news/detail-490757.html

到了这里,关于18. 算法之贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法与数据结构】--前言

    欢迎来到《算法与数据结构》专栏!这个专栏将引领您进入计算机科学领域中最重要、最精彩的领域之一:算法与数据结构。不管您是一名初学者,还是已经拥有一定编程经验的开发者,都可以从这里找到有益的知识和实践。 在计算机科学的世界里,算法和数据结构是至关重

    2024年02月07日
    浏览(246)
  • 元数据(Metadata),又称中介数据、中继数据

    元数据(Metadata),又称中介数据、中继数据,为描述数据的数据(data about data),主要是描述数据属性(property)的信息,用来支持如指示存储位置、历史数据、资源查找、文件记录等功能。元数据算是一种电子式目录,为了达到编制目录的目的,必须在描述并收藏数据的内容或特色

    2024年02月03日
    浏览(73)
  • 算法介绍 | 泛洪算法(Flood fill Algorithm)

    漫水填充算法、种子填充算法(Seed Fill) 用于确定连接到多维数组中给定节点的区域,可以用来标记或者分离图像的一部分,实现如Ps中自动选区功能。 顾名思义就像洪水漫过一样,把一块连通的区域填满。 当然水要能漫过需要满足一定的条件,可以理解为满足条件的地方

    2024年02月14日
    浏览(41)
  • 遗传算法(Genetic Algorithm,GA)

    这是一篇关于遗传算法的总结博客,包括算法思想,算法步骤,python实现的两个简单例子,算法进阶(持续更新ing)。 遗传算法的应用很多,诸如寻路问题,8数码问题,囚犯困境,动作控制,找圆心问题(在一个不规则的多边形中,寻找一个包含在该多边形内的最大圆圈的

    2023年04月17日
    浏览(44)
  • 遗传算法 (Genetic Algorithm, GA)

    遗传算法(Genetic Algorithm,简称GA)起源于对生物系统所进行的计算机模拟研究,是一种随机全局搜索优化方法,它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象,从任一初始种群(Population)出发,通过随机选择、交叉和变异操作,产生一群更适合

    2024年02月05日
    浏览(37)
  • Algorithm_01--C#递归算法

    ///递归算法本质: ///1、方法的自我调用 ///2、有明确的终止条件 ///3、每次调用时,问题规模在不断减少。通过递减,最终到达终止条件     问题:程序在输入1000后(即1到1000的和),程序会出现异常。 解答:百度后得出结论,栈溢出异常。 1、递归方法在每次调用自身时,

    2024年02月06日
    浏览(37)
  • 算法笔记:KM算法(Kuhn-Munkres Algorithm)

    带权二分图的最优匹配 问题 算法笔记:匈牙利算法_UQI-LIUWJ的博客-CSDN博客  匈牙利算法的一个问题是,找到的匹配不一定是最优匹配 因为算法将每个匹配对象的地位视为相同的,在这个前提下求解最大匹配 而很多时候,二部图连边是带权重的,在这个基础上的匹配才更贴近

    2023年04月09日
    浏览(37)
  • 【algorithm】算法基础课---二分查找算法(附笔记 | 建议收藏)

    🚀write in front🚀 📝个人主页:认真写博客的夏目浅石. 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 📣系列专栏:AcWing算法学习笔记 💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊 ✉️ 如果无聊的话,就来逛逛我的博客栈吧 stack-frame.cn 关于我

    2024年01月18日
    浏览(40)
  • Algorithm_01--C#递归算法01

    ///递归算法本质: ///1、方法的自我调用 ///2、有明确的终止条件 ///3、每次调用时,问题规模在不断减少。通过递减,最终到达终止条件     问题:程序在输入1000后(即1到1000的和),程序会出现异常。 解答:百度后得出结论,栈溢出异常。 1、递归方法在每次调用自身时,

    2024年02月06日
    浏览(49)
  • 关于Secure Hash Algorithm加密算法

    一、概述 SHA(Secure Hash Algorithm)加密算法是一种广泛应用的密码散列函数,由美国国家安全局(NSA)设计,用于保障数据的安全性和完整性。SHA算法经历了多个版本的更新,目前主要应用于各种网络安全和数据加密领域。 SHA在线加密 | 一个覆盖广泛主题工具的高效在线平台

    2024年02月04日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包