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

Question

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

我认为我可以解决这个问题的方法是在可能的结果上加一个项圈以防止出现无穷大的结果(如果苹果是 2 而橙子是 -1 那么对于任何和，都会有一个无限的解决方案但是如果我说两者都有一个限制，那么它就不能永远持续下去。)

下面是检测权重的 super 基本代码:

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

这是生成结果的代码(如果可能，第一个函数生成一个表，第二个函数组成实际结果。算法的详细信息/伪代码在这里:Can brute force algorithms scale?):

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)

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

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

编辑:有点不相关(如果有损于这个问题只是忽略，但既然你已经看过代码，有没有办法我可以用这个代码在我的机器上使用两个 cpus？现在当我运行它时，它只使用一个 cpu。我知道 python 中并行计算的技术方法，但不确定如何在逻辑上并行化该算法)

Answer 1

您可以通过更改 c 上的两个循环来限制结果

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

到

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

这将确保最终答案中的任何系数都是 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)