python 找零钱 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

算法训练找零钱

奇怪的是，每个人手里只有一张钞票（每张钞票的面值为25、50、100元），而且饭堂阿姨一开始没有任何零钱。...请问饭堂阿姨能否给所有人找零（假设饭堂阿姨足够聪明）输入格式　　第一行一个整数n，表示排队的人数。　　接下来n个整数a[1],a[2],...,a[n]。...Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int result=0; //初始钱

3051 0

动态规划应用--找零钱

问题描述找零问题，在贪心算法讲过。但是贪心不一定能得出最优解。假设有几种不同币值的硬币v1，v2，.……vn（单位是元）。如果要支付w元，求最少需要多少个硬币。...问题分析 2.1 回溯法求解 /** * @description: 找零钱，需要张数最少，回溯法 * @author: michael ming * @date: 2019/7/20 22:50...minPiece(18-10)} = 1 + min{minPiece(17),minPiece(9),minPiece(8)} DP（递归+备忘录）代码如下： /** * @description: 找零钱...2.3 DP状态转移表法 /** * @description: 找零钱，需要张数最少,dp状态表法 * @author: michael ming * @date: 2019/7/21 20:01

8571 0

您找到你想要的搜索结果了吗？

是的

没有找到

dp 类找零钱类问题

这类问题，需要维护，之前的状态，当前的状态是（当前 - 当前值）的上一个状态的最值相关零钱兑换给定不同面额的硬币 coins 和一个总金额 amount。...2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1 // 贪心思想，零钱兑换

6463 0

贪心法--零钱找零问题

问题描述：现在有2元、1元、0.5元、0.2元、0.1元、0.05元的纸币，如何才能使得找零的的张数最小基本思路;将纸币从大到小排序，尽可能地先找大额的； coins = [2,1,0.5,0.2,0.1,0.05

5612 0

用python实现零钱找零的三种方法

1.递归（recursion） def coins_changeREC(coin_values, change): """ 递归实现零钱找零 """ min_count...caching的递归 def coins_changeREC_cache(coin_values, change, known_counts=None): """ 添加了caching的递归零钱找零...coin_values, change, min_counts=None, last_used_coins=None): """ 利用动态规划(Dynamic Programming)的思想实现零钱找零...change])) change = change - last_used_coins[change] return ','.join(used_coins) 最后测试三种方法实现的零钱找零的时间效率...第一种没有添加caching的递归实现，完成一次63分零钱的找零竟然需要60s，简直无法忍受。而添加了caching的递归，一次找零0.22ms就完成了，这是生动的用空间换时间的算法。

1.9K3 0

1037 在霍格沃茨找零钱 (20 分)

1037 在霍格沃茨找零钱 (20 分) 如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可(Sickle)兑一个加隆(Galleon)，二十九个纳特(Knut...现在，给定哈利应付的价钱 P 和他实付的钱 A，你的任务是写一个程序来计算他应该被找的零钱。...输出格式：在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。...输入样例 1： 10.16.27 14.1.28 输出样例 1： 3.2.1 输入样例 2： 14.1.28 10.16.27 输出样例 2： -3.2.1 【我的代码】 // 1037 在霍格沃茨找零钱

5963 0

在霍格沃茨找零钱（20）

现在，给定哈利应付的价钱P和他实付的钱A，你的任务是写一个程序来计算他应该被找的零钱。输入格式：输入在1行中分别给出P和A，格式为“Galleon.Sickle.Knut”，其间用1个空格分隔。...输出格式：在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。

2602 0

1037 在霍格沃茨找零钱 (20 分)

本文链接：https://blog.csdn.net/shiliang97/article/details/99936776 1037 在霍格沃茨找零钱 (20 分) 如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统...现在，给定哈利应付的价钱 P 和他实付的钱 A，你的任务是写一个程序来计算他应该被找的零钱。...输出格式：在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。

4701 0

【PAT乙级】在霍格沃茨找零钱

现在，给定哈利应付的价钱 P 和他实付的钱 A，你的任务是写一个程序来计算他应该被找的零钱。...输出描述：在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。...直接无脑用Python，1~3行基操勿6，12行调用了divmod函数。...python真的是蒂花之秀，它这个divmod()函数把除数和余数运算结果结合起来，返回一个包含商和余数的元组(a // b, a % b)。...+P[1])*29+P[2] #哈利应付的价钱为Psum Asum = (A[0]*17+A[1])*29+A[2] #哈利实付的价钱为Asum Csum = Asum-Psum #哈利应该被找的零钱为

4581 0

蓝桥杯vip测试题-找零钱(解题思路以及解题代码)

奇怪的是，每个人手里只有一张钞票（每张钞票的面值为25、50、100元），而且饭堂阿姨一开始没有任何零钱。...请问饭堂阿姨能否给所有人找零（假设饭堂阿姨足够聪明）输入格式第一行一个整数n，表示排队的人数。接下来n个整数a[1],a[2],...,a[n]。...//找钱 for (int i = 0; i < qian.length; i++) { //如果第i个排队的人的钱足够 if (qian...danjia) { xianyoudanjia += qian[i]; //qian[i]>danjia：第i个人有的钱，...大于单价，就说明要找钱了 //(个人的钱 - 单价)=要找的钱，如果食堂阿姨现有的领钱>=要找的钱，说明可以找开 } else if (qian[i]

4964 0

PAT (Basic Level) Practice （中文）1037 在霍格沃茨找零钱 (20 分)

1037 在霍格沃茨找零钱 (20 分) 如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可(Sickle)兑一个加隆(Galleon)，二十九个纳特(Knut...现在，给定哈利应付的价钱 P 和他实付的钱 A，你的任务是写一个程序来计算他应该被找的零钱。...输出格式：在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。

5003 0

硬币找零问题

硬币找零问题是一种经典的背包问题。顾名思义，就是你去商店买完东西，售货员会给你用若干枚硬币找钱，如何使用这些硬币完成找零。

1.8K2 0

找零问题与动态规划

后来我发现在 leet code 也有类似的题，是个找零问题，就是不同面值的硬币组合成一个数有多少种情况。

1.1K1 0

OJ刷题记录：L1-802-一种高级的找零钱法(10分)

L1-802-一种高级的找零钱法(10分) 题目要求：如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可(Sickle)兑一个加隆(Galleon)，...现在，给定哈利应付的价钱 P 和他实付的钱 A，你的任务是写一个程序来计算他应该被找的零钱。...输出在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数；如果他带的钱刚好，那么输出"gang gang hao."。...样例输入 10.16.27 14.1.28 样例输出 3.2.1 解题思路：先将输入的应付和实付价格转换为最低单位 Knut，再相减得出应找零的价格对应的 Knut ，最后转换为 Galleon.Sickle.Knut

5522 0

Python高级算法——贪心算法（Greedy Algorithm）

Python中的贪心算法（Greedy Algorithm）：高级算法解析贪心算法是一种优化问题的解决方法，它每步选择当前状态下的最优解，最终希望通过局部最优的选择得到全局最优解。...在本文中，我们将深入讲解Python中的贪心算法，包括基本概念、算法思想、具体应用场景，并使用代码示例演示贪心算法在实际问题中的应用。基本概念 1....贪心算法的具体应用 3.1 找零钱问题找零钱问题是贪心算法的一个典型应用场景。通过选择面值最大的硬币，尽量减少找零的硬币数量。...6, 7, 9, 9] print(greedy_activity_selection(start_times, finish_times)) 应用场景贪心算法适用于一些具有贪心选择性质的问题，如找零问题...在Python中，我们可以应用贪心算法解决各种问题，如找零问题、活动选择问题等。理解贪心算法的基本概念和算法思想，对于解决一些具有贪心选择性质的问题具有指导意义，能够提高算法的效率。

2.2K1 0

11.动态规划（4）——找零问题

找零问题：需找零金额为W，硬币面值有(d1, d2, d3，…，dm)，最少需要多少枚硬币。　　问题：需找零金额为8，硬币面值有(1, 3, 2, 5)，最少需要多少枚硬币。...设F(j)表示总金额为j时最少的零钱数，F(0) = 0，W表示找零金额，有零钱一堆{d1, d2, d3，…，dm}。...Java 1 package com.algorithm.dynamicprogramming; 2 3 import java.util.Arrays; 4 5 /** 6 * 找零问题...33 System.out.println(Arrays.toString(count)); 34 return count[sum]; 35 } 36 } 　　Python3...1 #coding=utf-8 2 def charge_making(money, num): 3 ''' 4 找零问题 5 ''' 6 count =

2K10 0

leetcode-860-柠檬水找零

你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。...给定一个vector，里面装着前来购买5元柠檬水的顾客给的钱，只可能会给5元/10元/20元，而你要给他们找零。初始的时候，你手里面只有柠檬水，而没有任何零钱。...如果你能顺利完成所有找零工作（意味着第一个顾客只能给5元，方便你后续找零），那么返回true，如果不能完成所有找零工作，返回false。 2....每次有顾客来，判断要找多少零钱，检查一下当前的零钱能不能还，可以就找零，接着下一个顾客。在找零的过程中，当顾客给了20元，我们优先使用10元和5元的组合找零给顾客，而不是3张5元。...因为5元的零钱更为重要，当顾客使用10元的时候，我们只能找零5元零钱。如果优先使用3张5元去找零，那么极有可能最终剩下一大堆10元，而当顾客掏出10元购买柠檬水，我们却没有5元零钱来找零。

6924 0

【算法：贪心】：贪心算法介绍+基础题（四个步骤）；柠檬水找零（交换论证法）

对于10元的，要找一张五块钱。对于20元的，你可以找三张五块钱，也可以找一张五块钱和一张十块钱。 ●一开始没有零钱，也就是只能有顾客的钱来找零。...2.算法原理： 1.对于顾客给的五块钱，我们直接收下，不需要找零。 2.对于顾客付的十块钱，我们将十块钱收下，然后进行找五块钱。 3.对于顾客付的二十块钱，我们有两种找零的方式。...找零一：找三张五块钱的。找零二：找一张十块钱的，找一张五块钱的。从上面三种情况来看，五块钱有两种用途，十块钱只有一种用途（十块钱只能用来找零二十块钱的）。...贪心解的情况下就是在找零二十块钱的时候，如果有十块钱就先用十块钱找（即找零方法一）。如果没有十块钱，才用三张五块钱进行找零。...，贪心解用十块钱和五块钱进行找零，正确解用三张五块钱的进行找零。

8581 0

钞票找零-贪心,动态规划算法

php class Change { protected $moneyArr = [1, 2, 5, 10];//零钱 protected $changeMethod;//找零方法...89块钱,竟然需要89张1元的纸币,那能不能在能找零的情况,尽可能的将找的纸币数量缩小呢?...这时候我们就需要用到贪心算法贪心算法是指,在每一次情况下,都选择当前最优的解进行处理, 在这个场景里面,最优的解就应该是从大到小进行找零了,89块钱,先找最大面值的50块钱,然后找10块钱的,以此类推...php class Change { protected $moneyArr = [1, 2, 5, 10];//零钱 protected $changeMethod;//找零方法...php class Change { protected $moneyArr = [1, 2, 5, 10];//零钱 protected $changeMethod;//找零方法

1.1K2 0

Python实现5毛钱特效

一、前言 Python牛已经不是一天两天的事了，但是我开始也没想到，Python能这么牛。...我们需要使用到的模块主要有如下几个： pillow opencv moviepy paddlehub 我们都可以直接用pip安装： pip install pillow pip install opencv-python...用paddlehub抠图参考：别再自己抠图了，Python用5行代码实现批量抠图。...我们这里直接用pip安装cpu版本的： # 安装paddlepaddle python -m pip install paddlepaddle -i https://mirror.baidu.com/pypi

1.2K1 0

点击加载更多

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭