擅长:python、mysql、java
<p>把数量排成一个单子,分类。<a href="http://docs.python.org/2/library/bisect.html#searching-sorted-lists" rel="nofollow noreferrer">Use ^{<cd1>} to find an appropriate quantity.</a>计算较低的数量是否可以满足,如果不能满足,则选择下一个较高的数量。减去所选数量。如果仍然大于0,则返回<code>bisect</code>步骤。你知道吗</p>
<p><strong>编辑:</strong></p>
<pre><code>import bisect
qtys = [50, 100, 200, 500, 1000]
def sack(amt, qtys=qtys):
res = set()
while amt > 0:
pivot = bisect.bisect(qtys, amt)
if sum(qtys[:pivot]) >= amt:
amt -= qtys[pivot - 1]
res.add(pivot - 1)
else:
if sum(qtys[:pivot + 1]) < amt:
raise ValueError('Not enough items to fill the sack')
res.add(pivot)
amt -= qtys[pivot]
return res
print sack(150)
print sack(210)
print sack(1777)
print sack(530)
</code></pre>