不确定如何在数据生成算法中集成负数函数？

Question

我在控制我正在研究的数据生成算法的结果时遇到了一些麻烦。基本上，它从列表中获取值，然后列出所有不同的组合以获得特定的总和。到目前为止，代码运行良好（尚未测试使用许多变量对其进行缩放），但我需要允许负数包含在列表中。

我认为解决这个问题的方法是给可能的结果加上一个项圈，以防止无穷大的结果（如果苹果是2，橙子是-1，那么对于任何总和，都会有无限的解决方案，但如果我说有 这

这是检测权重的超级基本代码：

import math

data = [-2, 10,5,50,20,25,40]
target_sum = 100
max_percent = .8 #no value can exceed 80% of total(this is to prevent infinite solutions

for node in data:
    max_value = abs(math.floor((target_sum * max_percent)/node))
    print node, "'s max value is ", max_value

是生成结果的代码（第一个函数如果可能的话生成一个表，第二个函数组成实际结果。详细信息/伪代码的算法在这里：暴力算法可以扩展吗？）：

from collections import defaultdict

data = [-2, 10,5,50,20,25,40]
target_sum = 100
# T[x, i] is True if 'x' can be solved
# by a linear combination of data[:i+1]
T = defaultdict(bool)           # all values are False by default
T[0, 0] = True                # base case


for i, x in enumerate(data):    # i is index, x is data[i]
    for s in range(target_sum + 1): #set the range of one higher than sum to include sum itself
        for c in range(s / x + 1):  
            if T[s - c * x, i]:
                T[s, i+1] = True

coeff = [0]*len(data)
def RecursivelyListAllThatWork(k, sum): # Using last k variables, make sum
    # /* Base case: If we've assigned all the variables correctly, list this
    # * solution.
    # */
    if k == 0:
        # print what we have so far
        print(' + '.join("%2s*%s" % t for t in zip(coeff, data)))
        return
    x_k = data[k-1]
    # /* Recursive step: Try all coefficients, but only if they work. */
    for c in range(sum // x_k + 1):
       if T[sum - c * x_k, k - 1]:
           # mark the coefficient of x_k to be c
           coeff[k-1] = c
           RecursivelyListAllThatWork(k - 1, sum - c * x_k)
           # unmark the coefficient of x_k
           coeff[k-1] = 0

RecursivelyListAllThatWork(len(data), target_sum)

我的问题是，我不知道不知道在哪里/如何将我的限制代码集成到主代码中，以限制结果并允许负数。当我向列表中添加负数时，它会显示该负数，但不会将其包含在输出中。我认为这是因为它没有被添加到表（第一个函数）中，并且我不确定如何添加它（并且仍然保留程序结构，以便我可以使用更多变量来扩展它）。

预先感谢，如果有任何不清楚的地方，请告诉我。

编辑：有点不相关（如果偏离问题，请忽略，但既然您已经查看了代码，有没有办法我可以通过此代码利用我的机器上的两个CPU？现在，当我运行它时，它只使用一个CPU。我知道Python中并行计算的技术方法，但不知道如何逻辑上并行化这个算法）

Answer 1

您可以通过将 c 上的两个循环从

for c in range(s / x + 1):  

to

max_value = int(abs((target_sum * max_percent)/x))
for c in range(max_value + 1):

更改来限制结果。这将确保最终答案中的任何系数都是 0 到 max_value 范围内的整数（包括 0 和 max_value）。

添加负值的一个简单方法是将 s 上的循环从 更改为

for s in range(target_sum + 1):

请

R=200 # Maximum size of any partial sum
for s in range(-R,R+1):

注意，如果您这样做，那么您的解决方案将有一个额外的约束。
新的约束是每个部分加权和的绝对值必须<=R。

（您可以使 R 变大以避免此约束，从而减少解决方案的数量，但这会减慢执行速度。）

完整的代码如下所示：

from collections import defaultdict

data = [-2,10,5,50,20,25,40]

target_sum = 100
# T[x, i] is True if 'x' can be solved
# by a linear combination of data[:i+1]
T = defaultdict(bool)           # all values are False by default
T[0, 0] = True                # base case

R=200 # Maximum size of any partial sum
max_percent=0.8 # Maximum weight of any term

for i, x in enumerate(data):    # i is index, x is data[i]
    for s in range(-R,R+1): #set the range of one higher than sum to include sum itself
        max_value = int(abs((target_sum * max_percent)/x))
        for c in range(max_value + 1):  
            if T[s - c * x, i]:
                T[s, i+1] = True

coeff = [0]*len(data)
def RecursivelyListAllThatWork(k, sum): # Using last k variables, make sum
    # /* Base case: If we've assigned all the variables correctly, list this
    # * solution.
    # */
    if k == 0:
        # print what we have so far
        print(' + '.join("%2s*%s" % t for t in zip(coeff, data)))
        return
    x_k = data[k-1]
    # /* Recursive step: Try all coefficients, but only if they work. */
    max_value = int(abs((target_sum * max_percent)/x_k))
    for c in range(max_value + 1):
       if T[sum - c * x_k, k - 1]:
           # mark the coefficient of x_k to be c
           coeff[k-1] = c
           RecursivelyListAllThatWork(k - 1, sum - c * x_k)
           # unmark the coefficient of x_k
           coeff[k-1] = 0

RecursivelyListAllThatWork(len(data), target_sum)