Python 中贪婪方法的硬币找零问题

Question

我正在尝试在硬币找零问题中实现贪婪方法，但需要降低时间复杂度，因为编译器不会接受我的代码，而且由于我无法验证我什至不知道我的代码是否正确实际上是否正确。该函数应该 return 进行更改所需的注释总数。如果无法获得给定金额的找零，则 return -1。 Return 1 如果金额等于面额列表中的一种可用货币。

def make_change(denomination_list, amount):

    denomination_list.sort()
    n = len(denomination_list)
    i = n - 1
    ans = 0
    x = 0
    while i>= 0 :
        while denomination_list[i]<= amount:
            ans = +1
            amount -= denomination_list[i]
            i -= 1
        if amount == 0:
            x = 1
        elif amount<0:
            x = -1
    return x

    amount= 20
    denomination_list = [1,15,10]
    print(make_change(denomination_list, amount))

Answer 1

您希望尽可能减少列表索引的使用，并迭代列表本身。这是一个有效的代码：

# Pre-process denomination list before function, sorting in decreasing order
denomination_list = [1,15,10]
denomination_list.sort(reverse = True)
# Ensure ones are available for change (or infinite loop may result)
if denomination_list[-1] != 1:
    denomination_list.append(1)

def make_change(denomination_list, amount):
    change = []
    # Iterate through coins
    for coin in denomination_list:
        # Add current coin as long as not exceeding ampoiunt
        while amount:
            if coin <= amount:
                change.append(coin)
                amount -= coin
            else:
                break
    return change

amount= 43
print(make_change(denomination_list, amount))

这将适用于 amount 的非整数值，并将列出向下舍入金额的更改。

Python 中贪婪方法的硬币找零问题

Coin Change problem with Greedy Approach in Python

python

algorithm

greedy