通过递归在python中进行精确更改 [英] Exact change in python via recursion

问题描述

我被要求用 python 编写一个递归函数:

I'm asked to write a recursive function in python:

def exact_change( target_amount, L ):

其中输入 target_amount 是一个非负整数值，输入 L 是一个正整数值列表.然后，exact_change 应该返回 True 或 False:如果可以通过将 L 中的部分或全部值相加来创建 target_amount，则它应该返回 True.如果无法通过添加一些来创建 target_amount，它应该返回 False -或-L 中的所有值.

where the input target_amount is a single non-negative integer value and the input L is a list of positive integer values. Then, exact_change should return either True or False: it should return True if it’s possible to create target_amount by adding up some-or-all of the values in L. It should return False if it’s not possible to create target_amount by adding up some-or-all of the values in L.

例如，L 可以代表你口袋里的硬币，而 target_amount 可以代表物品的价格——在这种情况下，exact_change 会告诉你是否可以准确地支付物品.

For example, L could represent the coins you have in your pocket and target_amount could represent the price of an item – in this case, exact_change would tell you whether or not you can pay for the item exactly.

exact_change( 42, [25, 1, 25, 10, 5, 1] )

True

exact_change( 42, [25, 1, 25, 10, 5] )

False

我已经查找了一些改变问题"的解决方案，但我真的不知道如何编写这个函数.

I've looked up some of the 'change-making problem' solutions, but I can't really figure out how to program this function.

有人可以帮我吗?

推荐答案

通过反向排序 L，我们尝试先用完最大的硬币.这应该注意@MathiasEttinger 提到的情况.当然，在每次递归调用时重新排序已经排序的 L 是多余的，但排序必须发生在某个地方(如果它可以在第一次调用精确_change 之前发生就太好了).

By sorting L in reverse we try to use up the biggest coins first. This should take care about situations mentioned by @MathiasEttinger. For sure re-sorting the already sorted L at each recursive call is redundant, but sorting has to happen somewhere (it would be nice if it could happen before the first call to exact_change).

from copy import copy

def exact_change(target_amount, L):
    L = sorted(L, reverse=True)
    for v in L:
        if v == target_amount:
            return True
        else:
            if v < target_amount:
                L.remove(v)
                return exact_change(target_amount-v, L)
    else:
        return False


print exact_change( 42, [25, 1, 25, 10, 5, 1] )

print exact_change( 42, [25, 1, 25, 10, 5] )

这篇关于通过递归在python中进行精确更改的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！