Python 硬币兑换问题

硬币兑换问题：

给定总金额为A的一张纸币，现要兑换成面额分别为a1,a2,....,an的硬币，且希望所得到的硬币个数最少。

# 动态规划思想 dp方程式如下
# dp[0] = 0
# dp[i] = min{dp[i - coins[j]] + 1}, 且 其中 i >= coins[j], 0 <= j < coins.length
# 回溯法，输出可找的硬币方案
# path[i] 表示经过本次兑换后所剩下的面值，即 i - path[i] 可得到本次兑换的硬币值。

def changeCoins(coins, n):
  if n < 0: return None
  dp, path = [0] * (n+1), [0] * (n+1) # 初始化
  for i in range(1, n+1):
    minNum = i # 初始化当前硬币最优值
    for c in coins: # 扫描一遍硬币列表，选择一个最优值
      if i >= c and minNum > dp[i-c]+1:
        minNum, path[i] = dp[i-c]+1, i - c
    dp[i] = minNum # 更新当前硬币最优值

  print('最少硬币数:', dp[-1])
  print('可找的硬币', end=': ')
  while path[n] != 0:
    print(n-path[n], end=' ')
    n = path[n]
  print(n, end=' ')

if __name__ == '__main__':
  coins, n = [1, 4, 5], 22 # 输入可换的硬币种类，总金额n
  changeCoins(coins, n)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python 硬币兑换问题

    硬币兑换问题: 给定总金额为A的一张纸币,现要兑换成面额分别为a1,a2,....,an的硬币,且希望所得到的硬币个数最少. # 动态规划思想 dp方程式如下 # dp[0] = 0 # dp[i] = min{dp[i - coins[j]] + 1}, 且 其中 i >= coins[j], 0 <= j < coins.length # 回溯法,输出可找的硬币方案 # path[i] 表示经过本次兑换后所剩下的面值,即 i - path[i] 可得到本次兑换的硬币值. def ch

  • Python零钱兑换的实现代码

    Python零钱兑换的实现代码

    目录 题目: 题目分析: 解题思路: 解法一:递归 代码实现 代码注释 解法二: 题目: 给你一个整数数组 coins ,表示不同面额的硬币:以及一个整数 amount ,表示总金额. 计算并返回可以凑成总金额所需的 最少的硬币个数 .如果没有任何一种硬币组合能组成总金额,返回 -1 .你可以认为每种硬币的数量是无限的. 示例 1: 输入:coins = [1, 2, 5], amount = 11 输出:3 解释说明:11 = 5 + 5 + 1 示例 2: 输入:coins = [2], a

  • Python利用Canny算法检测硬币边缘

    Python利用Canny算法检测硬币边缘

    目录 一.问题背景 二.Canny 算法 (一).高斯平滑 (二)Sobel算子计算梯度 (三)非极大化抑制 (四)滞后边缘跟踪 一.问题背景 纸面上有一枚一元钱的银币,你能在 Canny 和 Hough 的帮助下找到它的坐标方程吗? 确定一个圆的坐标方程,首先我们要检测到其边缘,然后求出其在纸面上的相对位置以及半径大小. 在这篇文章中我们使用 Canny 算法来检测出纸面上银币的边缘. 二.Canny 算法 Canny 可以用于拿到图像中物体的边缘,其步骤如下 进行高斯平滑 计算图像梯度(记录

  • python爬虫_自动获取seebug的poc实例

    简单的写了一个爬取www.seebug.org上poc的小玩意儿~ 首先我们进行一定的抓包分析 我们遇到的第一个问题就是seebug需要登录才能进行下载,这个很好处理,只需要抓取返回值200的页面,将我们的headers信息复制下来就行了 (这里我就不放上我的headers信息了,不过headers里需要修改和注意的内容会在下文讲清楚) headers = { 'Host':******, 'Connection':'close', 'Accept':******, 'User-Agent':*

  • 使用Python编写类UNIX系统的命令行工具的教程

    引言 您是否能编写命令行工具?也许您可以,但您能编写出真正好用的命令行工具吗?本文讨论使用 Python 来创建一个强健的命令行工具,并带有内置的帮助菜单.错误处理和选项处理.由于一些奇怪的原因,很多人并不了解 Python? 的标准库具有制作功能极其强大的 *NIX 命令行工具所需的全部工具. 可以这样说,Python 是制作 *NIX 命令行工具的最佳语言,因为它依照"batteries-included"的哲学方式工作,并且强调提供可读性高的代码.但仅作为提醒,当您发现使用 Py

  • Python基于回溯法子集树模板解决找零问题示例

    Python基于回溯法子集树模板解决找零问题示例

    本文实例讲述了Python基于回溯法子集树模板解决找零问题.分享给大家供大家参考,具体如下: 问题 有面额10元.5元.2元.1元的硬币,数量分别为3个.5个.7个.12个.现在需要给顾客找零16元,要求硬币的个数最少,应该如何找零?或者指出该问题无解. 分析 元素--状态空间分析大法:四种面额的硬币看作4个元素,对应的数目看作各自的状态空间,遍历状态空间,其它的事情交给剪枝函数. 解的长度固定:4 解的编码:(x1,x2,x3,x4) 其中x1∈[0,1,2,3], x2∈[0,1,2,3,4

  • python数据处理实战(必看篇)

    python数据处理实战(必看篇)

    一.运行环境 1.python版本 2.7.13 博客代码均是这个版本 2.系统环境:win7 64位系统 二.需求 对杂乱文本数据进行处理 部分数据截图如下,第一个字段是原字段,后面3个是清洗出的字段,从数据库中聚合字段观察,乍一看数据比较规律,类似(币种 金额 万元)这样,我想着用sql写条件判断,统一转换为'万元人民币' 单位,用sql脚本进行字符串截取即可完成,但是后面发现数据并不规则,条件判断太多清洗质量也不一定,有的前面不是左括号,有的字段里面没有币种,有的数字并不是整数,有的没有万

  • EM算法的python实现的方法步骤

    EM算法的python实现的方法步骤

    前言:前一篇文章大概说了EM算法的整个理解以及一些相关的公式神马的,那些数学公式啥的看完真的是忘完了,那就来用代码记忆记忆吧!接下来将会对python版本的EM算法进行一些分析. EM的python实现和解析 引入问题(双硬币问题) 假设有两枚硬币A.B,以相同的概率随机选择一个硬币,进行如下的抛硬币实验:共做5次实验,每次实验独立的抛十次,结果如图中a所示,例如某次实验产生了H.T.T.T.H.H.T.H.T.H,H代表正面朝上. 假设试验数据记录员可能是实习生,业务不一定熟悉,造成a和b两种

  • Python实现霍夫圆和椭圆变换代码详解

    Python实现霍夫圆和椭圆变换代码详解

    在极坐标中,圆的表示方式为: x=x0+rcosθ y=y0+rsinθ 圆心为(x0,y0),r为半径,θ为旋转度数,值范围为0-359 如果给定圆心点和半径,则其它点是否在圆上,我们就能检测出来了.在图像中,我们将每个非0像素点作为圆心点,以一定的半径进行检测,如果有一个点在圆上,我们就对这个圆心累加一次.如果检测到一个圆,那么这个圆心点就累加到最大,成为峰值.因此,在检测结果中,一个峰值点,就对应一个圆心点. 霍夫圆检测的函数: skimage.transform.hough_circle

  • Python模拟随机游走图形效果示例

    Python模拟随机游走图形效果示例

    本文实例讲述了Python模拟随机游走图形效果.分享给大家供大家参考,具体如下: 在python中,可以利用数组操作来模拟随机游走. 下面是一个单一的200步随机游走的例子,从0开始,步长为1和-1,且以相等的概率出现.纯Python方式实现,使用了内建的 random 模块: # 随机游走 import matplotlib.pyplot as plt import random position = 0 walk = [position] steps = 200 for i in range

随机推荐