<pre><code>def find_combination(d,val):
"""(dict,int)->list
Given a dict with values as numbers, returns the combination of keys whose values sums up to "val"
In case no values form a perfect sum, picks up the next best case
"""
new_list = sorted(d.items(),key=lambda y: y[1],reverse=True)
result = []
while val > 0:
min_item = ''
for item in new_list:
if item[0] in result:
continue
new_diff = abs(val - item[1])
if not min_item or new_diff <= min_diff:
min_item = item[0]
min_diff = new_diff
min_val = item[1]
result.append(min_item)
val = val - min_val
return result
</code></pre>
<p>给予</p>
<pre><code>d={'loc2': 500.0, 'loc3': 200.0, 'loc1': 1000.0, 'loc4': 100.0, 'loc5': 50.0}
</code></pre>
<p>这给</p>
<pre><code>>>> combi.find_combination(d,150)
['loc4', 'loc5']
>>> combi.find_combination(d,210)
['loc3', 'loc5']
>>> combi.find_combination(d,1777)
['loc1', 'loc2', 'loc3', 'loc4']
>>> combi.find_combination(d,530)
['loc2', 'loc5']
>>> combi.find_combination(d,160)
['loc3']
</code></pre>
<p>必须指出它(极其)低效</p>