欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

动态规划-换钱的最少货币数(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