算法之Python实现 - 001 ：换钱的最少货币数 - Python

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题目】给定数组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!")

    arr.sort()

    arr.reverse()

    if aim == 0:

        print("Aim is 0, no need to change!")

    dp = np.zeros((len(arr),aim+1))

    i = 0

    j = 0

    left = aim

    maxval = MAXINT

    for j in range(1,aim+1):

        dp[0][j] = maxval

        if j-arr[0] >=0 and dp[0][j-arr[0]] != maxval:

            dp[0][j] = dp[0][j-arr[0]]+1

    for i in range(1,len(arr)):

        for j in range(1,aim+1):

            left = maxval

            if j-arr[i] >=0 and dp[i][j-arr[i]] != maxval:

                left = dp[i][j-arr[i]]+1

            dp[i][j] = min(left,dp[i-1][j])

    print('Need ',int(dp[len(arr)-1][aim]),' Coins.')

# ===CALL === #

a = [3,5,2]

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!")

    arr.sort()

    arr.reverse()

    if aim == 0:

        print("Aim is 0, no need to change!")

    dp = np.zeros((1,aim+1))[0]

    i = 0

    j = 0

    maxval = MAXINT

    for j in range(1,aim+1):

        dp[j] = maxval

        if j-arr[0] >=0 and dp[j-arr[0]] != maxval:

            dp[j] = dp[j-arr[0]]+1

    left = 0

    for i in range(1,len(arr)-1):

        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.')

# ===CALL === #

a = [5,2,3]

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!")

    arr.sort()

    arr.reverse()

    if aim == 0:

        print("Aim is 0, no need to change!")

    dp = np.zeros((1,aim+1))[0]

    i = 0

    j = 0

    maxval = MAXINT

    for j in range(1,aim+1):

        dp[j] = maxval

        if j-arr[0] >=0 and dp[j-arr[0]] != maxval:

            dp[j] = dp[j-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.')

# ===CALL === #

a = [5,2,3]

tar = 20

mincoin(a,tar)