在python中生成满足线性整数约束的列表

Question

在Python中，我有一个整数列表

w

，我想有效地生成所有整数列表，使得它们在

w

中的权重总和等于某个值

a

，即

 sum([i*j for i,j in zip(w,f)]) == a

即

w

与

f

的乘积由

a

固定。在这里，一切都受到

int

的重视。暴力版本是使用

itertools

:

from itertools import product

a = 20
w = [1,1,3,3]
rslt = []
for f in product(range(a), repeat=len(w)):
   if sum([i*j for i,j in zip(w,f)]) == a:
      rslt.append(list(f))

print(rslt)

然而，这与

a

的值的缩放比例非常差。有没有一种方法可以有效地生成

rslt

？我找不到直接用

itertools

施加约束的方法。从数学上讲，从已知向量

w

开始，我想找到所有向量

f

，使得它们的点积由

a

固定。

我提出了一个递归函数的想法，它可以在循环的给定阶段计算与

a

的差异，但我在实现时遇到了麻烦。如果有可能有一个实现也可以执行任意约束（例如二次），那就太棒了。

Answer 1

由于这被标记为“递归”，我想这个解决方案是可以接受的

def bb(a, w):
    # If target is 0, then all remaining numbers should be 0
    if a==0: return [(0,)*len(w)]
    # If target is non 0, then we need some remaining number, otherwise, empty set of solutions
    if len(w)==0: return []
    rslt=[]
    # branch & bound part. Just try with any possibility for first number
    # combined with (recursion) any possibility for the rest
    for first in range(0, a+1, w[0]):
        for rest in bb(a-first, w[1:]):
            rslt.append((first//w[0],)+rest)
    return rslt

在我的机器上，a=60，即 0.03 秒，而你的机器为 10 秒。 （另外，它有你缺少的解决方案。例如评论中提到的（0,20,0,0）。我假设非负数）