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
投稿猜你喜欢
- 表单在提交前我们通常会用客户端JS对其内容进行验证，通常都是写一个函数然后在onsumbit事件中调用，如下：<html><
- dict的很多方法跟list有类似的地方，下面一一道来，并且会跟list做一个对比嵌套嵌套在list中也存在，就是元素是list，在dict
一、文章概述本文将要讲述的是Python环境下如何用OpenCV检测人脸，本文的主要内容分为：1、检测图片中的人脸2、实时检测视频中出现的人- 需求背景：进行分值计算。如下图，如果只是一两个还好说，写写判断，但是如果有几十个，几百个，会不会惨不忍睹。而且，下面的还是三种情况。例如：解
- 每天换一个壁纸，每天好心情。# -*- coding: UTF-8 -*- from __future__ import unicode_l
- 这里推荐使用OTK脚本安装Oracle，会大大提高安装Oracle的成功系数。DescriptionoraToolKit is the Sw
- 转用一门新语言通常是一项大决策，尤其是当你的团队成员中只有一个使用过它时。今年 Stream 团队的主要编程语言从 Python 转向了 G
- 为什么要用jsonpath就跟为什么要用xpath一样，jsonpath的设计灵感来源于xpath。一个强大的json数据提取工具。让用户不
- web框架是什么?web开发框架是一组工具，同时也提供了非常多的资源，供软件开发人员构建和管理网站、提供web服务、编写web应用程序。它是
- 要说2017年什么技术最火爆，无疑是google领衔的深度学习开源框架Tensorflow。本文简述一下深度学习的入门例子MNIST。深度学
- ASP使用xmlhttp获取远程网页内容，解决乱码问题方法一：<％function getHTTPPage(url)on error
- (1)、back_log：要求 MySQL 能有的连接数量。当主要MySQL线程在一个很短时间内得到非常多的连接请求，这就起作用，然后主线程
- 有件东西我观察了很多年，那就是很少有开发者会去使用SQL Server中的一个非常有用的东西——EX
- 本文介绍TSV文件类型及其应用，同时介绍Golang语句读取TSV文件并转为struct的实现过程。认识TSV文件也许你之前不了解TSV文件
- 本文实例讲述了用python读写excel的方法。分享给大家供大家参考。具体如下：最近需要从多个excel表里面用各种方式整理一些数据，虽然
- 调用 <script language="javascript" src="xxx.asp?m
- 1、新建独立运行环境，命名为env[root@vultr ~]# mkdir projects # 测试的项目总目录[root@vultr
- 如何把程序打包为whl首先需要一个库：setuptools如果是conda环境的话，这个包是自带的，不需要另外安装。首先把需要打包的py文件
- 本文主要介绍的是MySQL慢查询分析方法，前一段日子，我曾经设置了一次记录在MySQL数据库中对慢于1秒钟的SQL语句进行查询。想起来有几个
- 本文为 djangorestframework-simplejwt 使用记录。(官方文档) 1. 安装 pip inst
