Python 硬币兑换问题
作者：GorillaNotes 发布时间：2022-04-03 06:30:09
标签：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)
来源：https://blog.csdn.net/XX_123_1_RJ/article/details/80353497
0
投稿猜你喜欢
- 本文实例讲述了php7 参数、整形及字符串处理机制修改。分享给大家供大家参考，具体如下：参数处理机制修改一、重复参数命名不再支持。重复的参数
- 是不是很烦每次注册网站或填写相关资料时都要重来一遍？其实会有很多自动填写工具能代劳。比如使用 Mac, 在 Safari 的表单中，它可以足
- Oracle DECODE函数功能很强，下面就为您详细介绍Oracle DECODE函数的用法，希望可以让您对Oracle DECODE函数
- 网上关于Python的音视频播放示例都集中在简单的多媒体库或者PyGame这样的游戏库，有些库使用简单，但功能单一，有些库功能丰富，支持的格
物质世界客观存在，而人的“视觉成像”是对当前世界的“唯心”重建。这种重建基于个人“经验”、“感知”和“集体意识”。最初科学家认为人类通过视觉- 你好，％用户名％！我叫Alex，我在机器学习和网络图分析（主要是理论）有所涉猎。我同时在为一家俄罗斯移动运营商开发大数据产品。这是我第一次在
- 介绍本期案例是带着大家制作一个属于自己的GUI图形化界面—>用于设计签名的哦(效果如下图)，是不是感觉很好玩，是不
- 问题：在使用mask_rcnn预测自己的数据集时，会出现下面错误：ResourceExhaustedError: OOM when allo
- 1.建表脚本1.1.建表DROP TABLE IF EXISTS `sys_region`;CREATE TABLE `sys_region
- 需求当需要同时ping/telnet多个ip时，可以通过引入ping包/telnet包实现，也可以通过go调用cmd命令实现，不过后者调用效
- 1. 谈谈Javascript的对象Javascript作为一种弱语言类型的语言，同时也是一种动态类型的语言。在使用Javascript的过
- 一个继承nn.module的model它包含一个叫做children()的函数，这个函数可以用来提取出model每一层的网络结构，在此基础上
- 前言range() 和 xrange() 是两个函数，可用于在 Python的 for 循环中迭代一定次数。在 Python 3 中，没有
- 本文实例讲述了pytorch制作自己的LMDB数据操作。分享给大家供大家参考，具体如下：前言记录下pytorch里如何使用lmdb的code
- 处理json中不带双引号key问题在解析网页json数据的时候,我发现python标准库json模块无法加载数据。如下面数据import j
- 本节我们首先来尝试识别最简单的一种验证码，图形验证码，这种验证码出现的最早，现在也很常见，一般是四位字母或者数字组成的，例如中国知网的注册页
- 在开发中我们经常遇到这样的需求，需要用户登录后才可以访问该页面，如果用户没有登录点击该页面时则自动跳转到登录页面，登录后又跳转到链接的页面而
- int(x, [base])功能：函数的作用是将一个数字或base类型的字符串转换成整数。函数原型：int(x=0)int(x, base=
- python-opencv获取二值图像轮廓及中心点坐标代码：groundtruth = cv2.imread(groundtruth_pat
- omitempty在go中的使用直接上代码：package mainimport ( "encoding/json&q
