贪心算法+练习

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

正值国庆之际,祝愿祖国繁荣昌盛,祝愿朋友一生平安!终身学习,奋斗不息!

目录

1.贪心算法简介

2.贪心算法的特点

3.如何学习贪心算法

题目练习(持续更新)

1.柠檬水找零(easy)

算法原理

代码实现

证明(交换论证法)


1.贪心算法简介

贪心策略:解决问题的一种策略,由局部最优->全局最优。

一般步骤:

1.把解决问题的过程分为若干步

2.解决每一步的时候,都选择当前“最优的”解法

3.“希望”得到全局最优解

例1:找零问题

有20,10,5,1面值货币若干张,如何用最少的张数支付46元?

贪心策略:每次选取尽可能大的货币

贪心算法+练习,数据结构与算法,贪心算法,算法

例2:背包问题

一个背包容量为8,有3种物品若干,选择要装的物品,使背包内物品总价值最大

贪心策略:每次选择单位体积价值尽可能大的物品。类似也可选择体积小(装更多的物品,总价值可能最大),价值大(每次选价值大的,总价值可能最大)。

贪心算法+练习,数据结构与算法,贪心算法,算法

通过贪心策略得到的结果是13,这并不是最优解(选取2个物品2,总价值14),所以贪心策略考虑的是局部最优,全局不一定最优。

2.贪心算法的特点

1.贪心策略没有标准,不同的问题选取的标准不同

2.贪心不一定得到全局最优解,正确的贪心策略需要被“证明”

证明方法:所有可用的数学证明方法


证明:找零问题的贪心策略

在例1中使用的贪心策略是每次选取尽可能大的货币,接下来证明它的正确性,即该贪心策略能够得出最优解。

分析最优情况下的性质

设不同面值货币使用张数分别为A,B,C,D

B有三种可能:B>2;B=2;B<2

当B>=2时,每两张10元货币都可以用一张20元货币代替,所以要使总货币张数最少,B只能<2。同理,C<2;D<5

贪心算法+练习,数据结构与算法,贪心算法,算法

设贪心策略下不同面值货币使用张数分别为a,b,c,d

现在只需证明a=A,b=B,c=C,d=D即可

根据贪心策略,显然a>=A。如果a>A,那么相差的每个20元,需要其它面值货币凑够,根据性质,B,C,D最大得到的总额是10+5+4=19元<20元,需要增加货币张数,不符合性质。所以a=A。

同理可证,b=B,c=C,d=D

贪心算法+练习,数据结构与算法,贪心算法,算法

综上,该贪心策略得到的就是最优解。

3.如何学习贪心算法

1放平心态

贪心算法并不是一种模版,它是一种解题策略。对于一些题目,想不到正确的贪心策略很正常。

2积累经验

学习贪心算法时,应该把重点放在贪心的策略上,对于每一道题目的贪心策略,我们应该当成经验去吸收,积累多了,我们“贪心的思维”自然就熟练了。

3尝试证明

一些贪心题目的原理比较简单,理解了贪心算法后基本不需要证明,对于一些较难的题目,我们学会解决它的贪心策略后可以尝试理解或证明它的正确性。

题目练习(持续更新)

1.柠檬水找零(easy)

题目链接:柠檬水找零

题目描述:

贪心算法+练习,数据结构与算法,贪心算法,算法

贪心算法+练习,数据结构与算法,贪心算法,算法

算法原理

1讨论找零情况:

贪心算法+练习,数据结构与算法,贪心算法,算法

2贪心策略

给20元找零有两种方式,需要选择最优的方式(完成更多的交易)

示例:已有5,5,5,10,下面的支付金额顺序是20,10

选择10+5方式找零,还剩5,5,可以用一个5给下一个10找零,true

选择5+5+5方式找零,给20找完后无剩余5,不能给下一个10找零,false

5元既可以给10元找零也可以给20元找零,所以本题的贪心策略是保留更多的5元,即给20找零优先使用10+5。

代码实现

用两个变量分别统计收下5,10的个数

找零(按分类讨论和贪心实现),5,10对应变量减去数量即可

无法找零返回false

C:

bool lemonadeChange(int* bills, int billsSize){
    int five = 0, ten = 0;

    for (int i = 0; i < billsSize; i++)
    {
        // 分类讨论
        if (bills[i] == 5)
            five++;
        else if (bills[i] == 10)
        {
            if (five == 0)
                return false;
            five--;
            ten++;
        }
        else
        {
            if (ten && five)// 贪心
            {
                ten--;
                five--;
            }
            else if (five >= 3)
            {
                five -= 3;
            }
            else
                return false;
        }
    }

    return true;
}

C++:

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;

        for (auto x : bills)
        {
            // 分类讨论
            if (x == 5)
                five++;
            else if (x == 10)
            {
                if (five == 0)
                    return false;
                five--;
                ten++;
            }
            else
            {
                if (ten && five)// 贪心
                {
                    ten--;
                    five--;
                }
                else if (five >= 3)
                {
                    five -= 3;
                }
                else
                    return false;
            }
        }

        return true;
    }
};

证明(交换论证法)

交换论证法:假设一种接近贪心算法的最优算法,通过交换它的一个步骤或元素,该算法的最优性不变,或者更接近贪心算法(贪心算法更优),那么贪心算法就是最优解。

贪心算法+练习,数据结构与算法,贪心算法,算法

证明该题目贪心策略的最优性:

假设最优解其中一步给20找零使用5+5+5

贪心算法+练习,数据结构与算法,贪心算法,算法讨论:

①最优解后面没有用贪心解的那个10找零

用10交换最优解给20找零的其中2个5,其仍然是最优解

贪心算法+练习,数据结构与算法,贪心算法,算法

②最优解后面有一次用了贪心解的10找零

给20找零的其中两个5可以与后面使用的10交换,其仍然最优

贪心算法+练习,数据结构与算法,贪心算法,算法

综上,该贪心算法是最优解(正确解)


贪心算法+练习,数据结构与算法,贪心算法,算法

其它贪心题目会根据个人学习情况不定时更新,敬请期待。

如果本文内容对你有帮助,可以点赞收藏,感谢支持,期待你的关注。文章来源地址https://www.toymoban.com/news/detail-716140.html

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

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

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

相关文章

  • 算法分析与设计考前冲刺 (算法基础、数据结构与STL、递归和分治、 动态规划、贪心算法、 回溯算法)

    算法分析与设计考前冲刺 算法基础 算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。 程序是算法用某种程序设计语言的具体的 具体实现 算法特征: 有穷性(有限步) 确定性 输入 输出 可行性(有限时间) 算法的复杂性: 时间复杂性 和空间复

    2024年02月02日
    浏览(44)
  • 数据结构与算法系列之习题练习

    💗 💗 博客:小怡同学 💗 💗 个人简介:编程小萌新 💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞 括号匹配问题。 用队列实现栈。 用栈实现队列。 设计循环队列。 有效的括号 //用栈来实现 //左括号进栈 右括号出栈并销毁如果不匹配则return //设置两个队列,入栈

    2024年02月11日
    浏览(47)
  • 数据结构算法练习 插入排序 冒泡排序

    插入排序 代码如下  package main import \\\"fmt\\\" func main() {     a := []int{4, 5, 6, 1, 3, 2}         b := insert(a)     for i := 0; i len(b); i++ {         fmt.Println(b[i])     } } func insert(a []int) []int {     if len(a) = 1 {                   如果数组长度小于等于1 不用排序直接返回          retur

    2024年02月08日
    浏览(58)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(54)
  • 数据结构练习-算法与时间复杂度

    -----------------------------------------------------------------------------------------------------------------------------          1. 设n是描述问题规模的非负整数,下列程序段的时间复杂度是( )。         A.O(logn) B.O(n^(1/2)) C.O(n) D.O(n²)         解析:         分析选项 A. O(log n) :这通常描

    2024年04月25日
    浏览(59)
  • 数据结构与算法--图(概念+练习题+解析)

    有向图 在有向图中有以下几点结论: 1.所有顶点的度数之和等于边数的二倍。 2.所有顶点的入度之和等于出度之和。 3.n个顶点的有向完全图有n(n-1)条边。 4.n个顶点的强连通图至少有n条边。 无向图 在无向图中有以下几点结论: 1.所有顶点的度数之和等于边数的二倍。 2.n个顶

    2024年02月04日
    浏览(45)
  • 【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)

    前面几篇文章介绍的是排序算法,现在让我们开始排序算法的专项练习。 1.希尔排序是稳定的算法。(错) 解析:稳定性是指如果两个元素在排序前后的相对顺序保持不变,那么这个排序算法就是稳定的。对于具有相同的元素,排序后它们的相对位置应该保持不变。

    2024年02月03日
    浏览(50)
  • 【数据结构】算法的时间复杂度和空间复杂度(下)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 空间复杂度也是一个数学表达式,是对一个算法在运行过程中 临时占用的额外的存储空间大小的量度 。 空间复杂度不是程序占用

    2023年04月19日
    浏览(87)
  • 【数据结构】 算法的时间复杂度和空间复杂度 (上)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何

    2023年04月14日
    浏览(41)
  • 【数据结构】算法的时间复杂度和空间复杂度 (上)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何

    2023年04月22日
    浏览(63)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包