贪心算法在找零问题中的应用

贪心算法在找零问题中的应用

  • 引言
  • a. 贪心算法求解找零问题
    • 算法设计
    • 算法证明
  • b. 硬币面额为c的幂时的贪心算法证明
    • 算法设计
    • 算法证明
  • c. 设计使贪心算法失效的硬币面额组合
  • d. 通用找零算法设计
    • 算法设计
    • 算法实现(伪代码)
    • 算法实现(C代码)
  • 结论

引言

找零问题是一个经典的优化问题,其目标是用最少的硬币找零给定的金额。贪心算法是解决这类问题的一种常用方法,其核心思想是在每一步选择中都采取最好或最优(即最有利)的选择,从而希望能够导致全局的最好或最优的解。在找零问题中,贪心算法的策略通常是根据硬币面额从大到小进行选择。

本文将围绕找零问题展开,通过贪心算法设计解决方案,并证明在特定条件下贪心算法的有效性。同时,也将探讨贪心算法失效的情况,并设计一种通用的找零算法。

在这里插入图片描述

a. 贪心算法求解找零问题

算法设计

假设我们有25美分、10美分、5美分和1美分四种面额的硬币。贪心算法的策略是尽可能多地使用面额较大的硬币,以减少硬币的总数。

  1. 初始化找零金额n
  2. 如果n大于等于25美分,则从n中减去25美分,并增加25美分硬币的数量。
  3. 如果n大于等于10美分且小于25美分,则从n中减去10美分,并增加10美分硬币的数量。
  4. 如果n大于等于5美分且小于10美分,则从n中减去5美分,并增加5美分硬币的数量。
  5. 如果n大于等于1美分且小于5美分,则从n中减去1美分,并增加1美分硬币的数量。
  6. 重复步骤2至5,直到n为0。

算法证明

要证明贪心算法在这种情况下能找到最优解,我们需要证明使用贪心策略找零所用的硬币数量是最少的。

假设存在一种更优的找零方式,它使用的硬币数量比贪心算法少。由于贪心算法总是优先使用面额较大的硬币,因此这种更优的方式必然在某个步骤中使用了比贪心算法更多的面额较小的硬币。然而,这会导致在后续步骤中可用的面额较大的硬币数量减少,从而需要更多的硬币来完成找零。这与假设更优的方式使用的硬币数量更少相矛盾。因此,贪心算法在这种情况下能找到最优解。

b. 硬币面额为c的幂时的贪心算法证明

算法设计

假设硬币面额是c的幂,即面额为C,c,…,C,c和k为整数,c>1,k≥1。在这种情况下,贪心算法依然优先使用面额较大的硬币。

算法证明

为了证明在这种情况下贪心算法总能得到最优解,我们可以使用数学归纳法。

基础情况:当k=1时,只有一种面额的硬币,贪心算法显然是最优的。

归纳假设:假设当k=m时,贪心算法是最优的。

归纳步骤:当k=m+1时,考虑使用贪心算法得到的找零方案。如果使用的最大面额的硬币数量为0,那么问题退化为k=m的情况,根据归纳假设,贪心算法是最优的。否则,如果我们使用至少一个最大面额的硬币,那么剩余的找零金额可以使用k=m的贪心算法来解决。由于归纳假设,这个子问题也是最优的。因此,当k=m+1时,贪心算法是最优的。

由数学归纳法,我们得出结论:当硬币面额为c的幂时,贪心算法总能得到最优解。

c. 设计使贪心算法失效的硬币面额组合

要使贪心算法不能保证得到最优解,我们需要设计一组特殊的硬币面额。一种常见的例子是使用1美分、3美分和4美分三种硬币。考虑找零7美分的情况,贪心算法会选择4美分和3美分,共需要两枚硬币。然而,最优解是使用两枚3美分硬币和一枚1美分硬币,共需要三枚硬币。因此,在这种情况下,贪心算法不能保证得到最优解。

d. 通用找零算法设计

算法设计

为了设计一个适用于任何k种不同面额硬币的通用找零算法,我们可以使用动态规划的方法。假设硬币面额为coins[k],找零金额为n

  1. 初始化一个大小为n+1的数组dp,其中dp[i]表示找零金额为i时所需的最少硬币数量。
  2. 对于每个金额i(从1到n),遍历所有硬币面额coins[j],如果coins[j]小于等于i,则更新dp[i]dp[i-coins[j]]+1dp[i]中的较小值。
  3. 返回dp[n]作为找零所需的最少硬币数量。

算法实现(伪代码)

function minCoins(coins, n):
    dp = array of size n+1 filled with ∞
    dp[0] = 0
    for i from 1 to n:
        for j from 0 to k-1:
            if coins[j] <= i:
                dp[i] = min(dp[i], dp[i-coins[j]] + 1)
    return dp[n]

算法实现(C代码)

#include <stdio.h>
#include <limits.h>

int minCoins(int coins[], int k, int n) {
    int dp[n+1];
    for (int i = 0; i <= n; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            if (coins[j] <= i) {
                dp[i] = fmin(dp[i], dp[i-coins[j]] + 1);
            }
        }
    }
    
    return dp[n];
}

int main() {
    int coins[] = {1, 3, 4};
    int k = sizeof(coins) / sizeof(coins[0]);
    int n = 7;
    printf("Minimum coins needed: %d\n", minCoins(coins, k, n));
    return 0;
}

结论

贪心算法在找零问题中是一种有效的策略,特别是在硬币面额为c的幂的情况下,它总能找到最优解。然而,当硬币面额不满足特定条件时,贪心算法可能会失效。为了处理更一般的情况,我们可以使用动态规划的方法设计一个通用的找零算法,该算法能够在任何硬币面额组合下找到最优解。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/575815.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【热门话题】PostCSS:现代前端开发中的CSS增强工具

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 PostCSS&#xff1a;现代前端开发中的CSS增强工具一、引言二、PostCSS简介2.1 核…

【树莓派4B】如何点亮树莓派的LED灯

在之前一系列文章中&#xff0c;使用python、行人入侵检测&#xff0c;确没有使用树莓派的硬件。控制引脚进行输出&#xff1a; 如何写python点亮led灯闪烁&#xff0c;我灯接在gpio13,GPIO19,gpio26。我都想闪烁。 你可以使用Python的GPIO库来控制树莓派上的LED灯。首先&…

安卓常用组件(启停活动页面、活动之间传递信息、收发应用广播、操作后台服务)

启停活动页面 Activity的启动和结束 页面跳转可以使用startActivity接口&#xff0c;具体格式为startActivity(new Intent(this, 目标页面.class));。 关闭一个页面可以直接调用finish();方法即可退出页面。 Activity的生命周期 页面在安卓有个新的名字叫活动&#xff0c;因…

【MySQL关系型数据库】基本命令、配置、连接池

目录 MySQL数据库 第一章 1、什么是数据库 2、数据库分类 3、不同数据库的特点 4、MySQL常见命令&#xff1a; 5、MySQL基本语法 第二章 1、MySQL的常见数据类型 1、数值类型 2、字符类型 3、时间日期类型 2、SQL语句分类 1、DDL&#xff08;数据定义语言&#x…

Relu激活函数

概念 神经网络中的每个神经元节点接受上一层神经元的输出值作为本神经元的输入值&#xff0c;并将输入值传递给下一层。在多层神经网络中&#xff0c;上层节点的输出和下层节点的输入之间具有一个函数关系&#xff0c;这个函数称为激活函数。 激活函数做的事情时把神经元的输…

STM32存储左右互搏 SDIO总线FATS文件读写SD/MicroSD/TF卡

STM32存储左右互搏 SDIO总线FATS文件读写SD/MicroSD/TF卡 SD/MicroSD/TF卡是基于FLASH的一种常见非易失存储单元&#xff0c;由接口协议电路和FLASH构成。市面上由不同尺寸和不同容量的卡&#xff0c;手机领域用的TF卡实际就是MicroSD卡&#xff0c;尺寸比SD卡小&#xff0c;而…

SN75107BDR 总线接收器 中文资料_PDF中文资料_参数_引脚图

SN75107BDR 规格信息&#xff1a; 制造商:Texas Instruments 产品种类:总线接收器 RoHS:是 接收机数量:2 Receiver 接收机信号类型:Differential 电源电压-最小:/- 4.75 V 电源电压-最大:/- 5.25 V 工作电源电流:30 mA 最小工作温度:0 C 最大工作温度: 70 C 封装 / 箱…

文旅IP孵化打造抖音宣传推广运营策划方案

【干货资料持续更新&#xff0c;以防走丢】 文旅IP孵化打造抖音宣传推广运营策划方案 部分资料预览 资料部分是网络整理&#xff0c;仅供学习参考。 PPT可编辑&#xff08;完整资料包含以下内容&#xff09; 目录 文旅IP抖音运营方案 1. 项目背景与目标 - 背景&#xff1a…

了解时间复杂度和空间复杂度

在学习数据结构前&#xff0c;我们需要了解时间复杂度和空间复杂度的概念&#xff0c;这能够帮助我们了解数据结构。 算法效率分为时间效率和空间效率 时间复杂度 一个算法的复杂度与其执行的次数成正比。算法中执行基础操作的次数&#xff0c;为算法的时间复杂度。 我们采…

Rust中的函数指针

什么是函数指针 通过函数指针允许我们使用函数作为另一个函数的参数。函数的类型是 fn &#xff08;使用小写的 ”f” &#xff09;以免与 Fn 闭包 trait 相混淆。fn 被称为 函数指针&#xff08;function pointer&#xff09;。指定参数为函数指针的语法类似于闭包。 函数指…

VIO外参标定方法总结

一、前言 VIO外参标定是指相机和IMU之间的转移矩阵的确定&#xff0c;包括33的旋转矩阵和3维平移向量。整体上分为离线标定和在线标定两类方法&#xff0c;这篇文章做一个总结&#xff0c;主要是经典的方法&#xff0c;记录其思想。 二、博文链接 1、离线标定方法 最基本的…

p0级故障-nptd和ntpdate用法

一、背景 绝对真实的大厂线上P0级故障经历分享。 某日凌晨3点&#xff0c;企业微信群变得热闹起来&#xff0c;想都不用想&#xff0c;作为互联网人&#xff0c;特别是运维相关的同学知道&#xff0c;肯定又是出故障了&#xff0c;并且这个故障还很大。 当前晚上我睡着了&#…

【Java EE】 文件IO的使用以及流操作

˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…

【Qt】error LNK2001: 无法解析的外部符号 “__declspec(dllimport)

参考&#xff1a;Qt/VS LNK2019/LNK2001&#xff1a;无法解析的外部符号_qt lnk2001无法解析的外部符号-CSDN博客 微软官方报错文档-链接器工具错误 LNK2019 __declspec error LNK2001: 无法解析的外部符号 "__declspec(dllimport) 原因 以这种为前缀的基本上跟库相关…

Visual Studio安装MFC开发组件

MFC由于比较古老了&#xff0c;Visual Studio默认没有这个开发组件。最近由于一些原因&#xff0c;需要使用这个库&#xff0c;这就需要另外安装。 参考了网上的一些资料&#xff0c;根据实际使用&#xff0c;其实很多步骤不是必须的。 https://zhuanlan.zhihu.com/p/68117276…

HarmonyOS开发实战(黑马健康系列一:欢迎页)

系列文章目录 &#xff08;零&#xff09;鸿蒙HarmonyOS入门&#xff1a;如何配置环境&#xff0c;输出“Hello World“ &#xff08;一&#xff09;鸿蒙HarmonyOS开发基础 &#xff08;二&#xff09;鸿蒙HarmonyOS主力开发语言ArkTS-基本语法 &#xff08;三&#xff09;鸿蒙…

沐风老师3DMAX一键相框生成插件安装使用方法教程

3DMAX一键相框生成插件使用教程 3DMAX一键相框生成插件&#xff0c;用于根据导入的图像文件以正确的比例从选定的图像中快速创建相框。只需点击几下鼠标&#xff0c;它就可以同时创建多个相框&#xff0c;在尺寸、轮廓、颜色和玻璃方面有许多选项。 支持Corona、Vray和标准材质…

Java基础(运算符)

运算符 运算符和表达式 运算符&#xff1a;对字面量或者变量进行操作的符号 表达式&#xff1a;用运算符把字面量或者变量连接起来&#xff0c;符合java语法的式子就可以称为表达式&#xff1b;不同运算符连接的表达式体现的是不同类型的表达式。 算术运算符&#xff08;加…

Unity 按下Play键后,Scene View里面一切正常,但是Game View中什么都没有 -- Camera Clear Flags的设置

问题如下所示。 最先遇到这个问题是我想用Unity开发一个VR 360-degree Image Viewer。在Scene View中可以看到球体&#xff0c;但是Game View什么都看不到。最后找到的原因是&#xff0c;我使用的shader是Skybox/Panorama&#xff0c; 需要把Main Camera的Clear Flags设置成Do…

灌区信息化解决方案-大型灌区信息化改造

系统方案 灌区信息化解决方案主要对灌区的水情、渠道流量、土壤墒情、气象等信息进行监测&#xff0c;对重点区域进行视频监控&#xff0c;同时对泵站、闸门进行远程控制&#xff0c;实现信息的测量、统计、分析、控制、调度等功能。为灌区管理部门科学决策提供了依据&#xff…