<p>另一个与现有的好答案相同的答案。我发现使用范围而不是目标+公差更简单,并且使用一个简单的(未优化的)递归解决方案,这似乎足够快速地找到您的用例的大约1000个答案。在</p>
<p>更改为使用生成器/产量或优化单值情况并不会改变所有结果所需的时间,尽管如果有管道,则可能会发现这很有用。在</p>
<pre><code>def fuzzy_coins(vals, lower, upper):
'''
vals: [Positive]
lower: Positive
upper: Positive
return: [[Int]]
Returns a list of coefficients for vals such that the dot
product of vals and return falls between lower and upper.
'''
ret = []
if not vals:
if lower <= 0 <= upper:
ret.append(())
else:
val = vals[-1]
for i in xrange(int(upper / val) + 1):
for sub in fuzzy_coins(vals[:-1], lower, upper):
ret.append(sub + (i,))
lower -= val
upper -= val
return ret
</code></pre>
<p>即使如此,在Python2.7和3.6中也需要大约100ms的时间</p>
^{pr2}$
<p>例如:用法:</p>
<pre><code>from __future__ import print_function
import pprint
import time
def main():
vals = [18.01, 42.01, 132.04, 162.05, 203.08, 176.03]
target = 1800.71
fuzz = .5
lower = target - fuzz
upper = target + fuzz
start = time.time()
coefs = fuzzy_coins(vals, lower, upper)
end = time.time()
pprint.pprint(sorted(
('%.2f' % sum(c * v for c, v in zip(coef, vals)), coef)
for coef in coefs
))
print('Took %.5fs to get %d results' % (end - start, len(coefs)))
</code></pre>