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

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