【零钱问题】C语言贪心算法分析(文末彩蛋)

简介: 【零钱问题】C语言贪心算法分析(文末彩蛋)

1.简介

       贪心算法是一种求局部最优解的方法,及将一个问题拆分为多个小步骤,对每一个小步骤进行考虑,不从大局出发,对于每一步去思考他的最优方案。这种思路经常用于求解最短路径问题,对每一个节点进行分组化考虑。本文将会采用一个简短的例子 ,来让读者能入门。并在原有基础上进行提升。在不久笔者还会对该算法进行拔高,链接将会作为引文放在这里。

2.问题叙述

       在天河世界,小远去商店想买一个本子,但碰到了爱刁难人的售货员。小远选中了一个本子,售价69元。他想去结账时候,售货员说‘我不接受太多硬币,你必须用最少的硬币数量来支付这69元,如果你可以做到,我就给你打对折”。这时候小远犯难了。小远手里只有10元,5元,2元的硬币,聪明的小朋友,你能告诉小远他该如何去付钱吗?(小远手里的钱足够多)

2.1问题分析

       小远手里有足够的钱,最大金额是10元。从贪心算法的角度去看,金额越大所需要的零钱数也就越少。我们就应该先去考虑最大金额的10元,然后顺次去考虑5元,最后就是去考虑最小金额2元,顺次遍历枚举去递增。当我们的金额与最小值相等时候就结束循环,然后将我们所需要的个数进行打印输出。

3.解题思路

3.1变量声明

       首先明确我们需要三个变量,来承接我们的零钱面值。

       然后明确我们需要三个变量,来作为我们的计数器,用于各个面值的遍历。

       其次明确我们需要一个变量,来承接我们的遍历总钱数。      

       接着明确我们需要一个变量,来承接我们的商品售价。

变量声明如下:

    int i,m,n;        //各个面值所需个数
    int a=10,b=5,c=2;//零钱面值金额
    int money=69,sum;//应付金额,遍历金额

3.2金额计算与判断

       最外层的i,m,n分别对应,c,b,a的个数。当我们的金额money与sum相等的时候就退出循环,并打印输出i,m,n的数值。

 接下来就是我们对sum进行求解了,我们将计数器的个数乘以面值再相加就是我们的面值了。

sum =a*n+b*m+c*i;    //总钱数求解
if(sum==money)break;//满足条件结束循环

       (这里解释一下原因:贪心算法总是考虑局部最优解,我们这里优先考虑最大面额的零钱,所以他的循环嵌套应该是在最内层。)

         

3.3核心算法

       这里我们使用循环来完成遍历,三个for循环进行嵌套。第一层是我们最小面值的计数,然后第二层就是我们中等面值的计数,然后最内层是我们最大面值的计数。具体原因我已经在3.2提到过了。

     

代码如下:

 for ( i = 0; i <10;i++ )
    {
        for ( m = 0; m<10;m++)
        {
            for ( n = 0; n < 10; n++)
            {
                sum =a*n+b*m+c*i;
                if(sum==money)break;
            }
            if(sum==money)break;
        }
        if(sum==money)break;
        else sum=0;
        }

4.完整代码

/*
1.我想买一本69元的图书
2.我有2元,5元,10元
3.我想要正好给他钱并且给他最少的硬币
思路:
    先全用7元硬币,然后判断时候大于7如果少于则继续,如果大于则将之前的值舍去,从新分配
*/
#include<stdint.h>
int main(int argc, char const *argv[])
{
    int i,m,n;
    int a=10,b=5,c=2;
    int money=69,sum;
    for ( i = 0; i <10;i++ )
    {
        for ( m = 0; m<10;m++)
        {
            for ( n = 0; n < 10; n++)
            {
                sum =a*n+b*m+c*i;
                if(sum==money)break;
            }
            if(sum==money)break;
        }
        if(sum==money)break;
        else sum=0;
        }
    printf("%d %d %d %d",i,m,n,sum);//出结果来
    return 0;
}

5.后记

       这是一个很简单的例子,仅仅是涉及到了贪心算法的入门,在后期我将会对文章进行优化,深度挖掘贪心算法的使用场景和我们的案例分析。

6.彩蛋

       多亏了我们各位聪明的小朋友,帮助小远成功买到了本子,有了这个程序小远以后再也不会被爱搞事的售货员刁难了。售货员看没有刁难到小远,含泪给小远打了对折。小远现在还在骨科挂瓶QAQ,在诊室写完了这篇文章。TAT

目录
相关文章
|
7天前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用,通过Node.js实现设备拓扑建模、路径分析与故障定位,提升网络可视化、可追溯性与运维效率,结合模拟实验验证其高效性与准确性。
64 3
|
4月前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
244 127
|
6月前
|
数据采集 机器学习/深度学习 算法
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
252 4
|
3月前
|
人工智能 自然语言处理 算法
2025 年 7 月境内深度合成服务算法备案情况分析报告
2025年7月,中央网信办发布第十二批深度合成算法备案信息,全国389款产品通过备案,服务提供者占比超七成。截至7月14日,全国累计备案达3834款,覆盖文本、图像、音视频等多模态场景,广泛应用于生活服务、医疗、金融等领域。广东以135款居首,数字人、AI客服等C端应用主导,民营企业成主力,国企聚焦公共服务。随着AI政策推动,备案已成为AI产品合规上线关键环节。
|
11月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
417 1
|
6月前
|
存储 监控 算法
员工行为监控软件中的 Go 语言哈希表算法:理论、实现与分析
当代企业管理体系中,员工行为监控软件已逐步成为维护企业信息安全、提升工作效能的关键工具。这类软件能够实时记录员工操作行为,为企业管理者提供数据驱动的决策依据。其核心支撑技术在于数据结构与算法的精妙运用。本文聚焦于 Go 语言中的哈希表算法,深入探究其在员工行为监控软件中的应用逻辑与实现机制。
148 14
|
7月前
|
自然语言处理 算法 安全
境内深度合成服务算法备案通过名单分析报告
本报告基于《境内深度合成服务算法备案通过名单》,分析了2023年6月至2025年3月公布的10批备案数据,涵盖属地分布、行业应用及产品形式等多个维度。报告显示,深度合成算法主要集中于经济发达地区,如北京、广东、上海等地,涉及教育、医疗、金融、娱乐等多行业。未来趋势显示技术将向多模态融合、行业定制化和安全合规方向发展。建议企业加强技术研发、拓展应用场景、关注政策动态,以在深度合成领域抢占先机。此分析旨在为企业提供参考,助力把握技术发展机遇。
境内深度合成服务算法备案通过名单分析报告
|
7月前
|
供应链 算法 搜索推荐
从公布的前十一批其他算法备案通过名单分析
2025年3月12日,国家网信办发布算法备案信息,深度合成算法通过395款,其他算法45款。前10次备案中,深度合成算法累计3234款,其他类别647款。个性化推送类占比49%,涵盖电商、资讯、视频推荐;检索过滤类占31.53%,用于搜索优化和内容安全;调度决策类占9.12%,集中在物流配送等;排序精选类占8.81%,生成合成类占1.55%。应用领域包括电商、社交媒体、物流、金融、医疗等,互联网科技企业主导,技术向垂直行业渗透,内容安全和多模态技术成新增长点。未来大模型检索和多模态生成或成重点。
从公布的前十一批其他算法备案通过名单分析
|
7月前
|
人工智能 自然语言处理 供应链
从第十批算法备案通过名单中分析算法的属地占比、行业及应用情况
2025年3月12日,国家网信办公布第十批深度合成算法通过名单,共395款。主要分布在广东、北京、上海、浙江等地,占比超80%,涵盖智能对话、图像生成、文本生成等多行业。典型应用包括医疗、教育、金融等领域,如觅健医疗内容生成算法、匠邦AI智能生成合成算法等。服务角色以面向用户为主,技术趋势为多模态融合与垂直领域专业化。
|
8月前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
126 3