动态规划-换钱的最少货币数(python实现)
程序员文章站
2022-07-09 23:28:22
算法题:换钱的最少钱币数最近在看左程云的《程序员代码面试指南》,感觉不错,题都分了类,很方便有目的的刷题,书里的代码都是java实现的,刚好最近在学习python,就用python去练习一下。1. 问题描述给定数组arr,其value代表货币面额,货币可无限张使用,给定一个整数aim作为要找的钱数,求组成aim的最少货币数举例:arr = [5, 2, 3]rest = 20则4张5元可以组成20元,此为最少钱币数量,返回42.解决方法1)暴力递归:从arr[0]开始,尝试每一种面值不同...
算法题:换钱的最少钱币数
最近在看左程云的《程序员代码面试指南》,感觉不错,题都分了类,很方便有目的的刷题,书里的代码都是java实现的,刚好最近在学习python,就用python去练习一下。
1. 问题描述
给定数组arr,其value代表货币面额,货币可无限张使用,给定一个整数aim作为要找的钱数,求组成aim的最少货币数
举例:
arr = [5, 2, 3]
rest = 20
则4张5元可以组成20元,此为最少钱币数量,返回4
2.解决方法
1)暴力递归:从arr[0]开始,尝试每一种面值不同张数。具体看源码
2)动态规划:首先确定了本题尝试是无后效性的,即现状态的返回值与怎么到达这个状态无关。然后确定可变参数:cur 和 rest,cur代表钱币面值数组位置,rest代表要找钱数,与01背包问题有一点类似,从下往上,从左往右的构造表。m[i][j]代表使用i~N号面值钱币,组成j元的最小数量,初始化这张表后,把表中数据计算完整。递归关系不易看出,但画出图后分析可以得出m[i][j]依赖于m[i+1]一整行的数据,再加以判断,可以发现,其实m[i][j]与同一行的数据也有一定联系:m[i][rest]就是m[i][rest - arr[i]]+1 和 m[i+1][j] 的最小值。
3.代码实现
暴力递归算法:
# 递归需要确定的i值,表明现在的位置
def minCores(arr, i, rest):
if i == len(arr):
return 0 if rest == 0 else -1
res = -1
k = 0
while k * arr[i] <= rest:
next = minCores(arr, i+1, rest - k*arr[i])
if next != -1: # 后续有效
res = next + k if res == -1 else min(res, next+k)
k += 1
return res
动态规划算法:
# 动态规划
def minCore(arr, aim):
m = [[-1 for i in range(aim+1)] for j in range(len(arr))]
m[len(arr)-1][0] = 0
i = len(arr) - 1
while i >= 0:
j = 0
while j <= aim:
# 看左边是否越界,且合法
if j - arr[i] >= 0 and m[i][j - arr[i]] != -1:
m[i][j] = m[i][j - arr[i]] + 1
# 看下方是否合法
if i+1 < len(arr) and m[i+1][j] != -1:
# m[i][j] = -1 说明左边不合法
if m[i][j] == -1:
m[i][j] = m[i+1][j]
# 如果都合法,取小的
else:
m[i][j] = m[i+1][j] if m[i][j] > m[i+1][j] else m[i][j]
j += 1
i -= 1
return m[0][aim]
主函数及结果
if __name__ == "__main__":
arr = [5, 2, 3]
i = 0
rest = 20
print(minCores(arr, i, rest))
print(minCore(arr, rest))
4
4
本文地址:https://blog.csdn.net/JYKgo/article/details/109922109
上一篇: Python学习笔记(八)
下一篇: 基于Java的记事本