决定给定数量的不同硬币是否可能形成给定数量的美元的代码

Question

(使用循环或递归)，我试图编写一个python函数，其中用户输入美元的数量(例如:1.25)和硬币的数量(例如:6)，然后该函数决定是否有可能使用确切给定的硬币数量来形成确切的美元数量，假设硬币是25美分(0.25)，10美分(0.10)，五美分(0.05)和便士(0.010)。该函数可以多次使用任何一种硬币，但使用的硬币总数必须等于传递给该函数的确切数字。
e。g:如果我们通过1美元和6个硬币的数量:应该返回True，因为我们可以使用(3个25美分+ 2个一角+ 1个镍币)

• 1.25美元使用5个硬币:True>>(5个季度)

• 1.25美元使用8枚硬币:True>>(2/5 + 5)

• 1.25美元使用7个硬币:错误。

• 我在脑海中有解决方案的想法，但无法将其转换为python代码:该函数必须开始迭代我们拥有的硬币组(从最高的硬币开始:0.25)并将其乘以传递的数字。虽然结果高于给定的美元数量，但传递的硬币数量应减少1。当我们到达(number * coin)的结果小于给定金额时，金额应该是(给定金额- (number * coin))，硬币的数量应该是(给定数字-到目前为止使用的数量)。我已经尝试了几天，使这个python代码。这是我目前所做的。'

def total(dollars, num):
dollars = float(dollars)
sofar = 0
num = round(num, 2)
coins = [0.25, 0.10, 0.05, 0.01]
possible = False 
if not possible:
for x in range(len(coins)):
if num * coins[x] == dollars:
possible = True 
elif num * coins[x] > dollars:
num -= 1 
sofar += 1
else:
dollars -= num * coins[x]
num = sofar 
return possible 

• 当我将(1.25,5)传递给函数>>真正的
• (1.25, 6)>>假
• (1.25, 7)>>假
• (1.25, 8)>>False(返回值错误)
  Thanks in advance

Answer 1

这是一个没有递归的工作解决方案，但确实使用了列表推导。不确定你的硬币集预计会增长到多大，因为这是计算所有组合的总和，所以它不会很好地缩放。

from itertools import combinations_with_replacement
list_of_coins = [0.1, 0.05, 0.25] # dimes, nickles, quarters
number_of_coins = 6 # as your example gives
sum_value = 1.0 # as your example gives
def will_it_sum(list_of_coins, number_of_coins, sum_value):
list_of_combos = list(combinations_with_replacement(iter(list_of_coins), number_of_coins))
summed_list = [sum(item) for item in list_of_combos]
summed_to_desired_value = [i for i in summed_list if i == sum_value]
if len(summed_to_desired_value) > 0:
return True
else:
return False
number_of_coins = 7
sum_value = 1.25
will_it_sum(list_of_coins, number_of_coins, sum_value)

Answer 2

使用python已经内置的解决方案下面。这可能不是一个很好的锻炼方案。

from itertools import combinations_with_replacement
def total(dollars, num):
cents = int(dollars*100)
coins = [25, 10, 5, 1]
return any(sum(comb) == cents for comb in combinations_with_replacement(coins, num))

或者，如果要返回组合:

from itertools import combinations_with_replacement
def total(dollars, num):
cents = int(dollars*100)
coins = [25, 10, 5, 1]
try:
return next(filter(lambda comb: sum(comb) == cents, combinations_with_replacement(coins, num)))
except StopIteration:
return None

Answer 3

这解决了不使用combinations的问题。这就是我上面描述的算法。你开始使用尽可能多的最大的硬币，然后你递归地看你是否可以填充较小的硬币。只要你找到匹配，你就赢了。

注意，我使用了一个帮助器，这样我就可以将美元转换为整数便士，以避免浮点问题。

coins = [25, 10, 5, 1]
def totalhelp(cents, num, which=0):
if which >= len(coins):
return False
cts = coins[which]
# What's the most of this coin we can use?
maxn = min(cents // cts, num)
for i in range(maxn,-1,-1):
amt = i * cts
if amt == cents:
return True
if totalhelp(cents-amt, num-i, which+1):
return True
return False
def total(dollars, num):
cents = int(dollars*100+0.5)
return totalhelp( cents, num )
print( total(1.25, 4 ) )
print( total(1.25, 5 ) )
print( total(1.25, 6 ) )
print( total(1.25, 7 ) )
print( total(1.25, 8 ) )

输出:

False
True
True
True
True