java - 如何将算法缩减为更小的部分以便我可以扩展它？

Question

我已经更新了这个问题(发现最后一个问题不清楚，如果你想引用它，请查看回滚历史)。到目前为止，当前的答案不起作用，因为我未能清楚地解释我的问题(抱歉，第二次尝试)。

目标:

尝试获取一组数字(正数或负数，因此需要限制特定变量的增长)并找到可用于得出特定总和的它们的线性组合。例如，要使用 [2,4,5] 得到 10 的总和，我们得到:

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

如何创建可扩展用于大量变量和 target_sums 的算法？如果给出算法，我可以自己编写代码，但如果有可用的库，我可以使用任何库，但更喜欢使用 java。

Answer 1

一个想法是一旦你将 T[z][i] 设置为 true 就跳出循环，因为你基本上只是在修改 T [z][i] 在这里，如果它确实变为 true，它将永远不会再被修改。

for i = 1 to k
    for z = 0 to sum:
        for j = z-x_i to 0:
            if(T[j][i-1]): 
                T[z][i]=true;
                break;

EDIT2:此外，如果我做对了，T[z][i] 取决于数组 T[z-x_i..0][i-1]。 T[z+1][i] 取决于 T[z+1-x_i..0][i-1]。因此，一旦您知道 T[z][i] 是否为 true，您只需检查一个附加元素 (T[z+1-x_i][ i-1]) 以了解 T[z+1][i-1] 是否为 true。

假设您表示 T[z][i] 是否由变量 changed 更新的事实。然后，您可以简单地说 T[z][i] = changed && T[z-1][i]。所以你应该在两个循环而不是三个循环中完成。这应该会使它更快。

现在，扩展它 - 现在 T[z,i] 仅依赖于 T[z-1,i] 和 T[z- 1-x_i,i-1]，所以要填充T[z,i]，你不需要等到整个(i-1) >第列已填充。一旦填充了所需的值，您就可以开始处理 T[z,i]。不了解细节我无法实现，但你可以试试这个方法。