通常，您可以使用big-
O表示法来分析算法的增长率来量化算法的扩展能力。当您说算法通过“蛮力”工作时，尚不清楚它将在多大程度上扩展。如果您的“蛮力”解决方案通过列出一组数据的所有可能子集或组合来工作，则几乎可以肯定不会缩放（它分别具有渐近复杂度O（2
n）或O（n！））。如果您的蛮力解决方案通过找到所有成对的元素并进行检查来起作用，则可以合理地缩放（O（n
2））。但是，如果没有有关算法工作原理的更多信息，这很难说。

您可能想看一下有关big-O的精彩文章，以此作为如何推理程序的长期可扩展性的起点。通常来说，增长率为O（n log n），O（n），O（logn）或O（1）的任何事物都具有非常好的比例，任何事物的增长率为O（n 2）或O（n 3）会扩展到一个点，并且任何增长率O（2 n）或更高的东西都不会扩展。

另一个选择是查找您要解决的问题，以了解其研究程度。众所周知，有些问题可以提供很好的解决方案，如果您的问题是其中的一种，则可能值得一看其他问题。也许有一个非常干净的非暴力解决方案，可以很好地扩展！推测其他一些问题根本没有可扩展的算法（所谓的
NP难题 ）。如果真是这样，那么您应该非常有信心没有办法获得可扩展的方法。

最后，您总是可以在Stack Overflow上提出一个新问题，以描述您要执行的操作并要求输入。也许社区可以比您最初预期的更有效地帮助您解决问题！

编辑： 给定您要解决的问题的描述，现在您正在为每个变量（从0到要定位的数字）进行一次for循环。该算法的复杂度为O（Uk），其中k为变量数，U为和。这种方法根本 无法
很好地扩展。在上述情况下引入每个新变量将使algori2thm的运行速度慢100倍，如果您想使用100个变量，这肯定不会很好地扩展！

但是，我认为有一个相当不错的算法，其运行时间为O（U 2
k），使用O（Uk）内存来解决该问题。直觉如下：假设我们要对1、2和4求和得到10。有很多方法可以做到这一点：

2 * 4 +  1 * 2 +  0 * 1
2 * 4 +  0 * 2 +  2 * 1
1 * 4 +  3 * 2 +  0 * 1
1 * 4 +  2 * 2 +  2 * 1
1 * 4 +  1 * 2 +  4 * 1
1 * 4 +  0 * 2 +  6 * 1
0 * 4 +  5 * 2 +  0 * 1
0 * 4 +  4 * 2 +  2 * 1
0 * 4 +  3 * 2 +  4 * 1
0 * 4 +  2 * 2 +  6 * 1
0 * 4 +  1 * 2 +  8 * 1
0 * 4 +  0 * 2 + 10 * 1

关键的观察结果是，我们可以将所有这些都写成和，但更重要的是，写成和，其中和中的每一项不大于上一项：

2 * 4 +  1 * 2 +  0 * 1 = 4 + 4 + 2
2 * 4 +  0 * 2 +  2 * 1 = 4 + 4 + 1 + 1
1 * 4 +  3 * 2 +  0 * 1 = 4 + 2 + 2 + 2
1 * 4 +  2 * 2 +  2 * 1 = 4 + 2 + 2 + 1 + 1
1 * 4 +  1 * 2 +  4 * 1 = 4 + 2 + 1 + 1 + 1 + 1
1 * 4 +  0 * 2 +  6 * 1 = 4 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  5 * 2 +  0 * 1 = 2 + 2 + 2 + 2 + 2
0 * 4 +  4 * 2 +  2 * 1 = 2 + 2 + 2 + 2 + 1 + 1
0 * 4 +  3 * 2 +  4 * 1 = 2 + 2 + 2 + 1 + 1 + 1 + 1
0 * 4 +  2 * 2 +  6 * 1 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  1 * 2 +  8 * 1 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  0 * 2 + 10 * 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

因此，这给出了有关如何生成所有可能的方法来求和目标的有趣观点。这个想法是先确定第一个系数，然后生成所有可能的方法来计算其余的总和。换句话说，我们可以递归地考虑问题。如果我们按x
1，x 2，…，x n的顺序列出变量，则可以尝试为x 1固定一些特定的系数，然后sum - c_1 x_1仅使用x 2，…，x
来解决求和的问题n。

到目前为止，这似乎还不是那么花哨-实际上，这正是您在上面所做的-
但是我们可以使用一个技巧。只要我们要递归地考虑这个问题，就让我们以相反的方式考虑这个问题。与其开始而不是sum尝试分解，不如说我们从0开始并试图建立所有可能的东西呢？

这是主意。假设我们已经预先知道了仅使用x 1的和就可以得出的所有数字。然后，对于介于0和sum（含）之间的每个数字k ，我们可以从x 2和x
1的任何组合中得出k，其中k-c 2 x 2是可以由x 1的组合得出的。但是，由于我们已经对此进行了预先计算，因此我们可以迭代所有可能的c
2合法值，计算k-c 2 x 2，看看我们是否知道该怎么做。假设我们存储了一个由布尔值组成的巨型U x（k +
1）表，使得表项[x，y]存储“我们是否可以将第一个y值（包括端值）相加，并精确地累加到U ?，”我们可以有效地填写表格。这称为 动态编程
，是功能强大的算法工具。

更具体地说，这是可能的工作方式。给定k个变量，创建值的U x（k + 1）表T。然后，对于所有x> 0，分别设置T [0] [0] = true和T [x]
[0] = false。这里的理由是T [0] [0]表示“我们可以使用前零个变量的线性组合？”
答案肯定是肯定的（空总和为零！），但是对于任何其他由无变量的线性组合组成的总和，我们绝对不能做到。

现在，对于i = 1 .. k，我们将尝试填写T [x] [i]的值。记住T [x] [i]的意思是“我们可以使x作为第一个i变量的线性组合吗？”
好吧，我们知道，如果存在一些系数c，则可以使用x 1，x 2，…，x i-1的线性组合来制作k-cx
i，则可以执行此操作。但是对于任何c来说，这仅仅是T [x-cx i ] [i-1]是否为真。因此我们可以说

for i = 1 to k
    for z = 0 to sum:
        for c = 1 to z / x_i:
            if T[z - c * x_i][i - 1] is true:
                set T[z][i] to true

检查循环，我们看到外循环运行k次，内循环sum每次迭代运行次数，最内层循环sum每次迭代最多运行。他们的乘积是（使用上面的符号）O（U 2
k），这比您最初使用的O（U k）算法要好得多。

但是，您如何使用此信息列出所有可能的方法来总结目标呢？这里的技巧是认识到，当其中许多组合无法使用时，您可以使用该表来避免浪费大量精力搜索每种可能的组合。

让我们来看一个例子。假设我们已经完全计算了此表，并希望列出所有解决方案。一种想法是考虑列出所有解决方案，其中最后一个变量的系数为零，然后当最后一个变量的系数为1时，依此类推。以前使用的方法的问题是，对于某些系数，可能根本没有任何解决方案。但是使用上面构造的表，我们可以删节那些分支。例如，假设我们要查看是否存在以系数为0的x
k开头的任何解。这意味着我们要询问是否有某种方式可以对前k-1个变量的线性组合求和，从而这些值的总和是sum。当且仅当T [sum]
[k-1]为真时，才有可能。如果是真的，那么我们可以递归地尝试以总计为的方式将系数分配给其余值sum。如果不是，那么我们跳过该系数并继续进行下一个。

递归地，看起来像这样：

function 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
        return

    /* Recursive step: Try all coefficients, but only if they work. */
    for c = 0 to sum / x_k:
       if T[sum - c * x_k][k - 1] is true:
           mark the coefficient of x_k to be c
           call RecursivelyListAllThatWork(k - 1, sum - c * x_k)
           unmark the coefficient of x_k

这将递归地列出所有有效的解决方案，并使用我们刚刚构建的表中的值来跳过大量的浪费工作。建立该表后，您可以通过将任务分配给多台计算机，让每台计算机列出全部解决方案的一个子集，然后并行处理它们，来分担这项工作。

希望这可以帮助！