Python中贪婪方法的硬币更换问题

Question

我试图在硬币兑换问题中实现贪婪方法，但需要降低时间复杂度，因为编译器不会接受我的代码，而且由于我无法验证，我甚至不知道我的代码是否正确。函数应返回进行更改所需的注释总数。如果无法获得给定金额的更改，则返回-1。如果金额等于面额列表中可用的货币之一，则返回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))

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