python - 使用特定值限制作为组合总和的数字组合

Question

python中是否有任何工具可以生成这些组合:

a=200
b=100

limit=500

组合是:

200,200,100  sum(200+200+100)<=500
200,100,100,100 sum(200,100,100,100)<=500  

Answer 1

>>> from itertools import product
>>> a = 200
>>> b = 100
>>> [x for i in range(1, limit/min((a,b))+1) # Py 2 use xrange for more efficiency
       for x in product((a,b), repeat=i)
       if sum(x) <= limit]
[(200,), (100,), (200, 200), (200, 100), (100, 200), (100, 100), (200, 200, 100), 
 (200, 100, 200), (200, 100, 100), (100, 200, 200), (100, 200, 100), 
 (100, 100, 200), (100, 100, 100), (200, 100, 100, 100), (100, 200, 100, 100), 
 (100, 100, 200, 100), (100, 100, 100, 200), (100, 100, 100, 100), 
 (100, 100, 100, 100, 100)]

函数形式如下:

>>> def combos(nums,limit):
        return [x for i in range(1, limit/min(nums)+1) 
                  for x in product(nums,repeat=i)
                  if sum(x) <= limit]

>>> combos(nums=(200,300,400),limit=700)
[(200,), (300,), (400,), (200, 200), (200, 300), (200, 400), (300, 200),
 (300, 300), (300, 400), (400, 200), (400, 300), (200, 200, 200), 
 (200, 200, 300), (200, 300, 200), (300, 200, 200)]

注意:此解决方案并未完全优化，因为它会生成所有可能的组合，即使较短的组合超过限制，也会继续生成较长的组合。