找零问题1-最少硬币

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

找零问题-最少硬币

【问题描述】
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。(你可以认为硬币的数量是无限的)
【输入形式】不同的面额的硬币,一个总金额
【输出形式】最少的硬币个数
【样例输入1】
coins = [1, 2, 5], amount = 11
【样例输出1】
3
【样例输入2】
coins = [2], amount = 3
【样例输出2】
-1
【样例输入3】
coins = [1], amount = 0
【样例输出3】
0
【样例输入4】
coins = [1], amount = 1
【样例输出4】
1

程序设计

C语言文章来源地址https://www.toymoban.com/news/detail-421933.html

#

到了这里,关于找零问题1-最少硬币的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 动态规划实现找零钱问题(C/++语言)

    设一硬币系统有n种面值,第i种硬币的面值和重量分别为pi​和wi​,硬币面值的单位为元,且有p1​p2​⋯pn​和p1​=1,现需要给别人找Y∈Z+元钱,试确定一找零钱方案,使得所找的硬币的总重量最轻。 要求使用如下动态规划思想 设Fk​(y)表示使用前k种硬币去找y元钱时所找硬

    2024年02月03日
    浏览(31)
  • 贪心算法在找零问题中的应用

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

    2024年04月23日
    浏览(35)
  • 《程序员面试金典(第6版)》 面试题 08.11. 硬币(动态规划,组合问题,C++)

    硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示例1: 输入: n = 5 输出:2 解释: 有两种方式可以凑成总金额: 5=5 5=1+1+1+1+1 示例2: 输入: n = 10 输出:4 解释: 有四种方式可以凑成总金额: 1

    2023年04月08日
    浏览(55)
  • 柠檬水找零【贪心算法-】

    柠檬水找零 在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。 每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。 注

    2024年02月10日
    浏览(36)
  • 力扣 860. 柠檬水找零

    题目来源:https://leetcode.cn/problems/lemonade-change/description/   C++题解:由于收到的钱币只有5,10,20三种,对于5元直接收,对于10元找零1张5元,对于20元找零15元,可以找零10+5或者3*5,但是5元用处较多,所有优先找零10+5。当5元不够的时候,return false。(其实可以不记录20元的数

    2024年02月17日
    浏览(38)
  • 【贪心算法】:LeetCode860.柠檬水找零

    朋友们、伙计们,我们又见面了,本专栏是关于各种算法的解析,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 C + + 专 栏   : C++ Linux 专 栏  : Linu

    2024年02月21日
    浏览(35)
  • 【每日一题】1523. 在区间范围内统计奇数数目,860. 柠檬水找零

    1523. 在区间范围内统计奇数数目 - 力扣(LeetCode) 给你两个非负整数  low  和  high  。请你返回   low   和   high   之间(包括二者)奇数的数目。 示例 1: 示例 2: 提示: 0 = low = high = 10^9          这是一道简单题。读完题目之后,要求奇数个数,最直接简单的想法就是

    2024年02月09日
    浏览(34)
  • javaScript蓝桥杯----猜硬币

    为了打发无聊的时间,小蓝开发了一款人机对战的猜硬币游戏,页面中一共有 9 个杯子,系统会随机挑选 3 个杯子在里面放入硬币,玩家通过输入含有杯子序号的字符串进行猜选,但是遇到了一些问题。 本题需要你帮助小蓝完成猜硬币游戏。 开始答题前,需要先打开本题的

    2024年02月08日
    浏览(35)
  • 【CSDN|每日一练】硬币划分

    有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱(n100000),有多少中组合可以组成n分钱? 输入整数n.(1=n=100000) 输出组合数,答案对1e9+7取模。

    2024年02月12日
    浏览(52)
  • 【动态规划】基础DP--硬币组合

    动态规划(Dynamic Programming,DP)一般是多阶段决策问题,把一个复杂问题分解为相对简单的子问题,再一一解决,得到原复杂问题的最优解。 求解DP问题的步骤:定义状态、状态转移、算法实现。 DP问题可以分为线性和非线性的。 线性DP。线性DP有两种方法:顺推与逆推。在

    2024年02月07日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包