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 orderdenomination_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:&nbsp; &nbsp; denomination_list.append(1)def make_change(denomination_list, amount):&nbsp; &nbsp; change = []&nbsp; &nbsp; # Iterate through coins&nbsp; &nbsp; for coin in denomination_list:&nbsp; &nbsp; &nbsp; &nbsp; # Add current coin as long as not exceeding ampoiunt&nbsp; &nbsp; &nbsp; &nbsp; while amount:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if coin <= amount:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; change.append(coin)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; amount -= coin&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; return changeamount= 43print(make_change(denomination_list, amount))这将适用于 的非整数值，amount并将列出向下舍入金额的变化。