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

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中并行计算的技术方法，但不太确定如何逻辑上并行化这个算法。）

算法优化并行计算组合算法数据生成限制条件暴力算法负数函数权重检测

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

1 个回答

撰写回答