算法之Python实现 - 002 ：换钱的最少货币数补充（每种货币只能使用一次）

谁借莪１个温暖的怀抱￠ 2021-12-15 04:55 176阅读 0赞

【题目】：给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币仅可以使用一张，再给定一个整数aim代表要找的钱数，求组成aim的最少货币数。

【代码1】：时间与额外空间复杂度O(N\*aim)

import numpy as np
    from xmlrpc.client import MAXINT
    
    def mincoin(arr,aim):
        if len(arr)<0:
            print("No coin provided for change!")
        if sum(arr)<aim:
            print("Coins provided not enough for change!")
        arr.sort()
        arr.reverse()
        if aim == 0:
            print("Aim is 0, no need to change!")
        i = 0
        j = 0
        maxval = 99#MAXINT
        dp = np.zeros((len(arr),aim+1))
        for i in range(1,len(arr)):
            dp[i] = np.array([99]*(aim+1))
            dp[i][0] = 0
            
        if arr[0]<= aim:
            dp[0][arr[0]] = 1
                
        left = 0
        for i in range(1,len(arr)):
            for j in range(1,aim+1):
                left = maxval
                if j-arr[i] >= 0 and dp[i-1][j-arr[i]] != maxval:
                    left = dp[i-1][j-arr[i]]+1
                dp[i][j] = min(left,dp[i-1][j])
        
        #print(dp)
        #print('Need ',int(dp[aim]),' Coins.')
        print('Need ',int(dp[len(arr)-1][aim]),' Coins.')
        
    # ===CALL === #
    a = [5,2,3,5,8]
    tar = 20
    mincoin(a,tar)

【代码2】：时间复杂度O(N\*aim)，额外空间复杂度O(aim)

import numpy as np
    from xmlrpc.client import MAXINT
    
    def mincoin(arr,aim):
        if len(arr)<0:
            print("No coin provided for change!")
        if sum(arr)<aim:
            print("Coins provided not enough for change!")
        arr.sort()
        arr.reverse()
        if aim == 0:
            print("Aim is 0, no need to change!")
        i = 0
        j = 0
        maxval = 99#MAXINT
        dp = np.array([99]*(aim+1))
        dp[0] = 0
            
        if arr[0]<= aim:
            dp[arr[0]] = 1
                
        left = 0
        for i in range(1,len(arr)):
            for j in range(1,aim+1):
                left = maxval
                if j-arr[i] >= 0 and dp[j-arr[i]] != maxval:
                    left = dp[j-arr[i]]+1
                dp[j] = min(left,dp[j])
        
        #print(dp)
        #print('Need ',int(dp[aim]),' Coins.')
        print('Need ',int(dp[aim]),' Coins.')
        
    # ===CALL === #
    a = [5,2,3,5,8]
    tar = 20
    mincoin(a,tar)

【代码3】：时间复杂度O(N\*aim)，额外空间复杂度O(aim)

同样的在原书也就是【代码2】的基础上，下面的执行效率会更高一点点，但是这种算法对于【代码1】的复杂度是有问题的。

import numpy as np
    from xmlrpc.client import MAXINT
    
    def mincoin(arr,aim):
        if len(arr)<0:
            print("No coin provided for change!")
        if sum(arr)<aim:
            print("Coins provided not enough for change!")
        arr.sort()
        arr.reverse()
        if aim == 0:
            print("Aim is 0, no need to change!")
        i = 0
        j = 0
        maxval = 99#MAXINT
        dp = np.array([99]*(aim+1))
        dp[0] = 0
            
        if arr[0]<= aim:
            dp[arr[0]] = 1
                
        left = 0
        for i in range(1,len(arr)):
            for j in range(j-arr[i],aim+1):
                left = maxval
                if dp[j-arr[i]] != maxval:
                    left = dp[j-arr[i]]+1
                dp[j] = min(left,dp[j])
        
        #print(dp)
        #print('Need ',int(dp[aim]),' Coins.')
        print('Need ',int(dp[aim]),' Coins.')
        
    # ===CALL === #
    a = [5,2,3,5,8]
    tar = 20
    mincoin(a,tar)

转载于:https://www.cnblogs.com/ElfoDigger/p/10605620.html