Python - 总结大于或等于某个值的数字组合

-1

我最近提出了以下面试问题，以Python回答 - 给定一个数量 - 值对列表，找到最佳组合它们的总和接近并且至少与某个提供的值一样大。例如，给定：[（1，$ 5），（3，$ 10），（2，$ 15）]，期望值为36美元，则答案为[（2，$ 15），（1， $ 10）]或[（1，$ 15），（2，$ 10），（1，$ 5）]。原因是40美元是可以实现的大于或等于36美元的最低总和，而这是实现这一总和的两种方式。Python - 总结大于或等于某个值的数字组合

我被难倒了。有没有人有办法解决吗？

来源

2017-08-31 iOSBeginner

你可以试试'itertools .combinations' – Wen

查找给定数量 - 数值对的所有组合，然后只取最小值[s] –

的数字是如此之小，你可以蛮力它：

In []: 
notes = [(1, 5), (3, 10), (2, 15)] 
wallet = [n for a, b in notes for n in [b]*a] 
combs = {sum(x): x for i in range(1, len(wallet)) for x in it.combinations(wallet, i)} 

target = 36 
for i in sorted(combs): 
    if i >= target: 
     break 
i, combs[i] 

Out[]: 
(40, (5, 10, 10, 15))

您可以扩展此对所有组合，只需更换与combs字典解析：

combs = {} 
for i in range(1, len(wallet)): 
    for x in it.combinations(wallet, i): 
     combs.setdefault(sum(x), set()).add(x) 

... 
i, combs[i] 

Out[]: 
(40, {(5, 10, 10, 15), (10, 15, 15)})

来源

2017-08-31 02:37:30 AChampion

Python - 总结大于或等于某个值的数字组合

回答

相关问题