在Python中递归地实现“最小数量的硬币”

给定一个硬币列表,它们的值(c1,c2,c3,… cj,…)和总和i。

找到总和为i的最小数量的硬币(我们可以根据需要使用任意数量的一种类型的硬币),或者报告无法选择以总和为S的方式选择硬币。

我昨天刚刚被介绍给动态编程,我试图为此编写代码。

# Optimal substructure: C[i] = 1 + min_j(C[i-cj])

cdict = {}

def C(i, coins):

if i <= 0:

return 0

if i in cdict:

return cdict[i]

else:

answer = 1 + min([C(i - cj, coins) for cj in coins])

cdict[i] = answer

return answer

在此,C [i]是金额“

i”的最佳解决方案。程序中可用的硬币为{c1,c2,…,cj,…},我增加了递归限制,以避免最大递归深度超过错误。但是,该程序仅给某人一个正确的答案,当不可能解决时,它并不表示这样做。

回答:

这是一个很大的算法问题,但老实说,我认为您的实现不正确,或者很抱歉,我可能不了解您函数的输入/输出。

这是实现的修改版本。

def C(i, coins, cdict = None):

if cdict == None:

cdict = {}

if i <= 0:

cdict[i] = 0

return cdict[i]

elif i in cdict:

return cdict[i]

elif i in coins:

cdict[i] = 1

return cdict[i]

else:

min = 0

for cj in coins:

result = C(i - cj, coins)

if result != 0:

if min == 0 or (result + 1) < min:

min = 1 + result

cdict[i] = min

return cdict[i]

这是我尝试解决类似问题的尝试,但是这次返回了硬币列表。我最初从递归算法开始,该算法接受一个总和和一个硬币列表,如果找不到这种配置,它可能返回一个硬币数量最少的列表,或者返回无。

def get_min_coin_configuration(sum = None, coins = None):

if sum in coins: # if sum in coins, nothing to do but return.

return [sum]

elif max(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do.

return None

else: # check for each coin, keep track of the minimun configuration, then return it.

min_length = None

min_configuration = None

for coin in coins:

results = get_min_coin_configuration(sum = sum - coin, coins = coins)

if results != None:

if min_length == None or (1 + len(results)) < len(min_configuration):

min_configuration = [coin] + results

min_length = len(min_configuration)

return min_configuration

好的,现在让我们看看是否可以通过使用动态编程(我称之为缓存)来改善它。

def get_min_coin_configuration(sum = None, coins = None, cache = None):

if cache == None: # this is quite crucial if its in the definition its presistent ...

cache = {}

if sum in cache:

return cache[sum]

elif sum in coins: # if sum in coins, nothing to do but return.

cache[sum] = [sum]

return cache[sum]

elif max(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do.

cache[sum] = None

return cache[sum]

else: # check for each coin, keep track of the minimun configuration, then return it.

min_length = None

min_configuration = None

for coin in coins:

results = get_min_coin_configuration(sum = sum - coin, coins = coins, cache = cache)

if results != None:

if min_length == None or (1 + len(results)) < len(min_configuration):

min_configuration = [coin] + results

min_length = len(min_configuration)

cache[sum] = min_configuration

return cache[sum]

现在让我们运行一些测试。

assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in

[({'sum':25, 'coins':[1, 5, 10]}, [5, 10, 10]),

({'sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]),

({'sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]),

({'sum':123, 'coins':[5, 10, 25]}, None),

({'sum':100, 'coins':[1,5,25,100]}, [100])] ])

如果此测试不够强大,您也可以这样做。

import random

random_sum = random.randint(10**3, 10**4)

result = get_min_coin_configuration(sum = random_sum, coins = random.sample(range(10**3), 200))

assert sum(result) == random_sum

没有这样的硬币组合可能等于我们的random_sum,但我相信它的可能性很小…

我肯定那里有更好的实现方式,我试图强调可读性而不是性能。祝好运。

了先前的代码,它有一个小错误,它应该检查最小硬币而不是最大硬币,重新编写符合pep8标准的算法,并[]在找不到组合的情况下返回代替None

def get_min_coin_configuration(total_sum, coins, cache=None):  # shadowing python built-ins is frowned upon.

# assert(all(c > 0 for c in coins)) Assuming all coins are > 0

if cache is None: # initialize cache.

cache = {}

if total_sum in cache: # check cache, for previously discovered solution.

return cache[total_sum]

elif total_sum in coins: # check if total_sum is one of the coins.

cache[total_sum] = [total_sum]

return [total_sum]

elif min(coins) > total_sum: # check feasibility, if min(coins) > total_sum

cache[total_sum] = [] # no combination of coins will yield solution as per our assumption (all +).

return []

else:

min_configuration = [] # default solution if none found.

for coin in coins: # iterate over all coins, check which one will yield the smallest combination.

results = get_min_coin_configuration(total_sum - coin, coins, cache=cache) # recursively search.

if results and (not min_configuration or (1 + len(results)) < len(min_configuration)): # check if better.

min_configuration = [coin] + results

cache[total_sum] = min_configuration # save this solution, for future calculations.

return cache[total_sum]

assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in

[({'total_sum':25, 'coins':[1, 5, 10]}, [5, 10, 10]),

({'total_sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]),

({'total_sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]),

({'total_sum':123, 'coins':[5, 10, 25]}, []),

({'total_sum':100, 'coins':[1,5,25,100]}, [100])] ])

以上是 在Python中递归地实现“最小数量的硬币” 的全部内容, 来源链接: utcz.com/qa/406598.html

回到顶部