是否有任何“技巧”来加速非常大的背包组合类型概率的采样？

更新： 由于涉及大量数据（15k +项目），我已经意识到下面的问题无法以当前forms回答。 我刚刚发现，我试图帮助的小组让它运行一个月然后终止它以使用结果（这就是为什么他们希望在更快的时间内获得更多结果）。 这对我来说似乎很疯狂，因为他们只使用前几组数据（大型列表中的最后一项永远不会被使用）。 所以我正在修改这个问题以获得预期输出的样本（解决方案的近似不是完全解决方案）。 在较短的时间内完成此操作的最佳方法是什么？ 他们似乎想要一个多样化的结果样本，是遗传算法工作还是某种采样技术？ 问题的其余部分保持不变（相同的输入/输出），但我现在不是在寻找完整的解决方案集（因为它在一生中永远不会完成，但我希望各种解决方案的各种解决方案都可以）。

---

我的问题不完全是一个背包问题，但它非常接近。 基本上，我试图找到等于特定值的X项的每个组合。 我从我的一个朋友那里听说过这个问题，他在一个小型的学校研究实验室工作，这个过程已经运行，大约需要25天才能完成。 看起来很可怕，所以我提出了帮助（对我来说很好，我可以学习并帮助一些非常好的人），所以我想出了如何通过multithreading来扩展它（我将包括下面的代码），这个减少了他们处理时间的几天，但我仍然不满意所以我只是移植我的代码在GPU上工作但我感到不满意（虽然他们很高兴，因为它更快，我捐赠了我的旧显卡）因为我只是在利用硬件而不是任何算法。 现在，我只是通过检查值是否等于总数来强制执行结果，如果确实如此，则保存结果，如果它没有继续处理它。

那么在这样的背景下，我能做些什么来加速算法呢？ 我的直觉告诉我不，因为他们需要每一个组合，从逻辑上看，计算机必须处理每个组合（数十亿），但我之前看到了惊人的事情，即使是一个小的加速也可以在处理的日子里有所作为。

我喜欢超过10个版本的代码，但这里是一个使用multithreading的Java版本（但这个和gpu之间的逻辑几乎相同）。

基本逻辑：

for (int c = 100; c >= 0; c--) { if (c * x_k == current.sum) { //if result is correct then save solutions.add(new Context(0, 0, newcoeff)); continue; } else if (current.k > 0) { //if result is not equal but not end of list then send to queue contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff)); } } 

完整代码：

 import java.util.Arrays; import java.util.ArrayDeque; import java.util.Queue; import java.util.concurrent.ConcurrentLinkedQueue; import java.util.concurrent.LinkedBlockingDeque; import java.util.concurrent.Callable; import java.util.concurrent.ExecutorService; import java.util.concurrent.ThreadPoolExecutor; import java.util.concurrent.TimeUnit; public class MixedParallel { // pre-requisite: sorted values !! private static final int[] data = new int[] { -5,10,20,30,35 }; // Context to store intermediate computation or a solution static class Context { int k; int sum; int[] coeff; Context(int k, int sum, int[] coeff) { this.k = k; this.sum = sum; this.coeff = coeff; } } // Thread pool for parallel execution private static ExecutorService executor; // Queue to collect solutions private static Queue solutions; static { final int numberOfThreads = 2; executor = new ThreadPoolExecutor(numberOfThreads, numberOfThreads, 1000, TimeUnit.SECONDS, new LinkedBlockingDeque()); // concurrent because of multi-threaded insertions solutions = new ConcurrentLinkedQueue(); } public static void main(String[] args) { System.out.println("starting.."); int target_sum = 100; // result vector, init to 0 int[] coeff = new int[data.length]; Arrays.fill(coeff, 0); mixedPartialSum(data.length - 1, target_sum, coeff); executor.shutdown(); // System.out.println("Over. Dumping results"); while(!solutions.isEmpty()) { Context s = solutions.poll(); printResult(s.coeff); } } private static void printResult(int[] coeff) { StringBuffer sb = new StringBuffer(); for (int i = coeff.length - 1; i >= 0; i--) { if (coeff[i] > 0) { sb.append(data[i]).append(" * ").append(coeff[i]).append(" + "); } } System.out.println(sb); } private static void mixedPartialSum(int k, int sum, int[] coeff) { int x_k = data[k]; for (int c = 0; c  0) { if (data.length - k < 2) { mixedPartialSum(k - 1, sum - c * x_k, newcoeff); // for loop on "c" goes on with previous coeff content } else { // no longer recursive. delegate to thread pool executor.submit(new ComputePartialSum(new Context(k - 1, sum - c * x_k, newcoeff))); } } } } static class ComputePartialSum implements Callable { // queue with contexts to process private Queue contexts; ComputePartialSum(Context request) { contexts = new ArrayDeque(); contexts.add(request); } public Void call() { while(!contexts.isEmpty()) { Context current = contexts.poll(); int x_k = data[current.k]; for (int c = 0; c  0) { contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff)); } } } return null; } } } 

以下是数据/方法的一些特征：

• 所有数字都是短裤（没有数字似乎超过+/- 200的值）
• 有重复（但没有零值）
• for循环将系数限制为100（这是一个很难的数字并且告诉它不会改变）。 这限制了结果
• 项目数量有限，但其变量由我的朋友实验室决定。 我一直在测试2对组合，但我的朋友告诉我他们使用30-35对（它不是涉及整个数据集的组合）。 这也限制了失控的结果
• 我的朋友提到他们所做的后期处理涉及删除包含少于30个系数或超过35的所有结果。在我当前的代码中，如果newcoeff变量超过一个数字（在这种情况下为35），我就会中断，但也许有一种方法可以不均匀处理结果低于30. 这可能是减少处理时间的一个重要领域。 现在看起来它们会产生很多无用的数据来达到他们想要的数据。
• 他们的数据集是10k-15k项目（负/正）
• 我只收到3个项目，两个列表（一个数据和一个用于标识数据的ID号）和一个目标总和。 然后我保存一个包含该列表中所有数据组合的文件。
• 我提供了帮助，因为这部分花了最长的时间，在数据来到我之前他们做了一些事情（尽管他们自己不生成数据）并且一旦我发送文件他们将自己的逻辑应用于它并处理它。 因此，我唯一的重点是获取3个输入并生成输出文件。
• 使用线程和GPU已经减少了在一周内完成的问题，但我在这里寻找的是改进算法的想法，因此我可以利用软件而不仅仅是硬件gpu来提高速度。 从代码中可以看出，它现在只是暴力。 理想情况下，我希望有线程的建议。

Update2：我认为问题本身很简单/常见，但问题是大规模运行，所以这是我们进行测试时获得的真实数据（它没有它得到的那么大但是它的大约3,000个项目所以如果你想要测试你不必自己生成它）：

 private static final int target_sum = 5 * 1000; private static final List data = Arrays.asList( -193, -138, -92, -80, -77, -70, -63, -61, -60, -56, -56, -55, -54, -54, -51, -50, -50, -50, -49, -49, -48, -46, -45, -44, -43, -43, -42, -42, -42, -42, -41, -41, -40, -40, -39, -38, -38, -38, -37, -37, -37, -37, -37, -36, -36, -36, -35, -34, -34, -34, -34, -34, -34, -34, -33, -33, -33, -32, -32, -32, -32, -32, -32, -32, -32, -31, -31, -31, -31, -31, -31, -31, -30, -30, -30, -30, -30, -29, -29, -29, -29, -29, -29, -29, -29, -29, -28, -28, -28, -28, -27, -27, -27, -27, -26, -26, -26, -26, -26, -26, -25, -25, -25, -25, -25, -25, -25, -25, -24, -24, -24, -24, -24, -24, -24, -24, -24, -24, -23, -23, -23, -23, -23, -23, -23, -23, -22, -22, -22, -22, -22, -22, -22, -22, -22, -21, -21, -21, -21, -21, -21, -21, -20, -20, -20, -20, -20, -20, -20, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 36, 36, 36, 36, 37, 37, 38, 39, 39, 39, 40, 41, 41, 41, 41, 41, 42, 42, 43, 43, 44, 45, 45, 46, 47, 47, 48, 48, 49, 49, 50, 54, 54, 54, 55, 55, 56, 56, 57, 57, 57, 57, 57, 58, 58, 58, 59, 60, 66, 67, 68, 70, 72, 73, 73, 84, 84, 86, 92, 98, 99, 105, 114, 118, 120, 121, 125, 156); 

我正在学习编程和算法，所以如果我错过了什么或者什么都没有意义，请告诉我。 请注意我明白这似乎是不可能的，因为大数据，但它不是（我已经看到它运行，它的变化已运行多年）。 请不要让比例分散真实问题，如果你使用10个变量，比我的10变量蛮力快10％，那么我相信它对更大的数据会更快。 我不打算把灯吹灭，我正在寻找小改进（或更大的设计改进），提供更快的结果（我会研究每一个建议）。 如果有任何需要放松的假设让我知道。

谢谢！

Answer 1

这使用动态编程来解决您在示例中给出的相同问题。 它已被更新以通过跟踪值的索引而不是其值来处理重复值，并更正忽略某些解决方案的错误。

 public class TurboAdder { private static final int[] data = new int[] { 5, 10, 20, 25, 40, 50 }; private static class Node { public final int index; public final int count; public final Node prevInList; public final int prevSum; public Node(int index, int count, Node prevInList, int prevSum) { this.index = index; this.count = count; this.prevInList = prevInList; this.prevSum = prevSum; } } private static int target = 100; private static Node sums[] = new Node[target+1]; // Only for use by printString. private static boolean forbiddenValues[] = new boolean[data.length]; public static void printString(String prev, Node n) { if (n == null) { System.out.println(prev); } else { while (n != null) { int idx = n.index; // We prevent recursion on a value already seen. if (!forbiddenValues[idx]) { forbiddenValues[idx] = true; printString((prev == null ? "" : (prev+" + "))+data[idx]+"*"+n.count, sums[n.prevSum]); forbiddenValues[idx] = false; } n = n.prevInList; } } } public static void main(String[] args) { for (int i = 0; i < data.length; i++) { int value = data[i]; for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) { for (int newsum = sum+1; newsum <= target; newsum++) { if (sums[newsum - sum] != null) { sums[newsum] = new Node(i, count, sums[newsum], newsum - sum); } } } for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) { sums[sum] = new Node(i, count, sums[sum], 0); } } printString(null, sums[target]); } } 

Answer 2

您尝试解决的问题称为数字分区 。 这是背包问题的一个特例。 如果值都是整数并且您试图获得值M，那么您可以在O（n * M）时间内找到单个解。 列举所有组合可能是指数的，因为可能存在指数数量的解。

Answer 3

你可能想检查“ 动态编程 ”的概念，动态编程主要是节省了大量的时间，不像正常的递归; 因为它通过以2D数组的forms保存它来避免重新计算值，所以本教程可能对您有所帮助

注意：背包问题被认为是动态编程的引入问题，搜索“背包动态编程”会对你有所帮助

Answer 4

如果您不需要详尽而精确的解决方案，可以尝试近似解决问题。 然后程序将以伪多项式或甚至多项式时间运行。

见http://en.m.wikipedia.org/wiki/Knapsack_problem#Approximation_algorithms

Answer 5

要通过动态编程解决这个问题，所有成本都需要是非负整数，并且只要您尝试实现的总成本，就需要一个数组 – 数组的每个元素都对应于其偏移量所代表的成本的解决方案在数组中。 由于您需要所有解决方案，因此数组的每个元素都应该是解决方案的最后组件的列表。 您可以通过要求解决方案的最后一个组件的成本至少与解决方案的任何其他组件一样多来减小此列表的大小。

鉴于此，一旦填充了长度为N的数组，就可以通过考虑100个多重性中每个可能的项来填充条目N + 1。 对于每个此类项目，您从N + 1中减去（多次乘以成本）并查看为了获得N + 1的总成本，您可以使用此项目加上任何成本N + 1-thisCost的解决方案。 所以你看一下arrays – 回到你已经填写的一个条目 – 看看是否有N + 1-thisCost的解决方案，如果有的话，以及当前的成本*多样性是否至少与某个项目一样高在数组[N + 1-thisCost]中，您可以为项目添加条目，在偏移量N + 1处添加多重性。

一旦你将数组扩展到你的目标成本，你可以从数组[finalCost]处理后备词，查看那里的答案并减去它们的成本，找出要查找的完整数组[finalCost – costOfAnswerHere]解。

这个解决方案没有明显的并行版本，但有时动态编程的加速比足够好，可能仍然更快 – 在这种情况下，很大程度上取决于最终成本的大小。

这与普通的动态编程有点不同，因为你想要每个答案 – 希望它仍然会给你一些优势。 想想看，最好只在arrays中有一个可能/不可能的标志，说明是否存在该arrays偏移的解决方案，然后在追溯时重复检查可能的组合。

Answer 6

给出的样本数据中有137个唯一值（忽略重复）。

如果你承认通过调整系数几乎可以将从随机数据中提取的30个不同值的几乎任何组合按摩到至少一个有效解决方案中，则必须至少有C（137,30）= 1.54E30解决方案条款（另有5.31E30,31条款，1.76E31,32条款，5.60E31,33条款等）。

所以，如果你的目标只是一个有效解决方案的抽样，而不是一个不可能的详尽列表，那么我认为一个理想的方法是随机选择你的目标条件数，然后调整它们的系数达到目标值，以产生一个单个样品，并重复所需数量的样品。

以下是应用此技术的程序。 在我相当适中的笔记本电脑（1.3Ghz AMD E-300）上，我在2.249秒内制作了15000个独特的解决方案，每个样本32个术语。

 import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; import java.util.Random; import java.util.TreeMap; public class ComboGen { private static final int[] data = { -193, -138, -92, -80, -77, -70, -63, -61, -60, -56, -56, -55, -54, -54, -51, -50, -50, -50, -49, -49, -48, -46, -45, -44, -43, -43, -42, -42, -42, -42, -41, -41, -40, -40, -39, -38, -38, -38, -37, -37, -37, -37, -37, -36, -36, -36, -35, -34, -34, -34, -34, -34, -34, -34, -33, -33, -33, -32, -32, -32, -32, -32, -32, -32, -32, -31, -31, -31, -31, -31, -31, -31, -30, -30, -30, -30, -30, -29, -29, -29, -29, -29, -29, -29, -29, -29, -28, -28, -28, -28, -27, -27, -27, -27, -26, -26, -26, -26, -26, -26, -25, -25, -25, -25, -25, -25, -25, -25, -24, -24, -24, -24, -24, -24, -24, -24, -24, -24, -23, -23, -23, -23, -23, -23, -23, -23, -22, -22, -22, -22, -22, -22, -22, -22, -22, -21, -21, -21, -21, -21, -21, -21, -20, -20, -20, -20, -20, -20, -20, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -19, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -18, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -17, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -14, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -13, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -12, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -10, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -9, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -7, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -6, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -4, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 36, 36, 36, 36, 37, 37, 38, 39, 39, 39, 40, 41, 41, 41, 41, 41, 42, 42, 43, 43, 44, 45, 45, 46, 47, 47, 48, 48, 49, 49, 50, 54, 54, 54, 55, 55, 56, 56, 57, 57, 57, 57, 57, 58, 58, 58, 59, 60, 66, 67, 68, 70, 72, 73, 73, 84, 84, 86, 92, 98, 99, 105, 114, 118, 120, 121, 125, 156 }; private static Map buildCounts(int[] rawData) { Map buckets = new TreeMap(); int i = 0; for (i = 0; i < rawData.length; i++) { if (buckets.containsKey(rawData[i])) { buckets.put(rawData[i], buckets.get(rawData[i]) + 1); } else { buckets.put(rawData[i], 1); } } weights = new int[buckets.size()]; counts = new int[buckets.size()]; i = 0; for (Entry entry : buckets.entrySet()) { weights[i] = entry.getKey(); counts[i] = entry.getValue(); i++; } return buckets; } private static int[] weights; private static int[] counts; private static Random random = new Random(System.nanoTime()); private static int[] placeChips(int[] chips, int targetPairs) { int unplaced = targetPairs; int[] placements = new int[unplaced]; Arrays.fill(chips, 0); if (unplaced > chips.length) { throw new IllegalStateException("Coefficient pairs must not exceed unique data values."); } while (unplaced > 0) { int idx = random.nextInt(counts.length); if (chips[idx] == 0) { chips[idx] = 1 + random.nextInt(100); unplaced--; } } int ppos = 0; for (int cpos = 0; cpos < chips.length; cpos++) { if (chips[cpos] > 0) { placements[ppos++] = cpos; } } return placements; } static int sum(int[] chips) { int sum = 0; for (int i = 0; i < chips.length; i++) { sum += weights[i] * chips[i]; } return sum; } public static void adjustFactors(int[] chips, int[] placements, int target) { int sum = sum(chips); Map weightIdx = new HashMap(); for (int placement : placements) { weightIdx.put(weights[placement], placement); } while (sum != target) { // System.out.print(sum + ","); int idx = 0; if ((sum > target) && weightIdx.containsKey(sum - target) && (chips[weightIdx.get(sum - target)] > 1)) { idx = weightIdx.get(sum - target); } else if ((sum < target) && weightIdx.containsKey(sum - target) && (chips[weightIdx.get(sum - target)] > 1)) { idx = weightIdx.get(sum - target); } else if ((sum > target) && weightIdx.containsKey(target - sum) && chips[weightIdx.get(target - sum)] < 100) { idx = weightIdx.get(target - sum); } else if ((sum < target) && weightIdx.containsKey(target - sum) && chips[weightIdx.get(target - sum)] < 100) { idx = weightIdx.get(target - sum); } else { idx = placements[random.nextInt(placements.length)]; } int weight = weights[idx]; if (sum < target) { if (weight > 0 && chips[idx] < 100) { chips[idx]++; sum += weight; } else if (weight < 0 && chips[idx] > 1) { chips[idx]--; sum -= weight; } } else { if (weight > 0 && chips[idx] > 1) { chips[idx]--; sum -= weight; } else if (weight < 0 && chips[idx] < 100) { chips[idx]++; sum += weight; } } } } private static String oneRandomSet(int targetSum, int targetPairs) { int[] chips = new int[counts.length]; int[] placements = placeChips(chips, targetPairs); adjustFactors(chips, placements, targetSum); int sum = sum(chips); StringBuffer sb = new StringBuffer(); for (int placement : placements) { sb.append(weights[placement]); sb.append(" * "); sb.append(chips[placement]); sb.append(" + "); } sb.setLength(sb.length() - 2); sb.append(" = "); sb.append(sum); sb.append("\n"); return sb.toString(); } public static void main(String[] ARGV) { int targetSum = 5000; int targetPairs = 32; int targetResults = 15000; // Produce this many solutions buildCounts(data); StringBuffer sb = new StringBuffer(); long timer = System.nanoTime(); for (int i = 0; i < targetResults; i++) { sb.append(oneRandomSet(targetSum, targetPairs)); } double seconds = (System.nanoTime() - timer) / 1000000000d; double millisPerSol = 1000 * seconds / targetResults; System.out.println(sb.toString()); System.out.println(String.format("%d solutions in %1.3f seconds @ %1.3f millis per sol", targetResults, seconds, millisPerSol)); } } 

Answer 7

编辑：我保留这个答案（至少现在）来保留评论post

OK, I’m confused, but I’ll post my thoughts anyway and edit/delete them later if I’m wrong. If I’m really far off the mark, you can just say so and I’ll delete this whole answer.

First of all, it looks to me that since zero is a valid data value and zero works in all positions, you are getting yourself into extra trouble computing all those combinations. Worse, it looks to me like your algorithm has an actual bug in that it will miss some combinations where a combination of items toward the beginning of the list sum to zero, since you terminate that thread of investigation once you find a combination of items toward the end of the list that yields the target sum.

Next, it looks to me like for every item in the list, you are trying 100 (actually 101) different values: x*100, x*99, …, x*0. If I am right, than it follows that the size of the problem space is 100^n where n is the number of data elements. There is no possible way you are examining that for n=100 let alone n=10,000. The only way your program could even be terminating is because you find sums at the end of the list and terminate those threads of investigation. (Oh right, now you tell me you terminate threads when the number of elements with non-zero coefficients exceeds 3, no 50, no 60, no some variable number. The problem space is still too big.)

In fact, by my count, your test data has 283 zeros. So you can add 100^283 combinations of those data elements times [1,100] to any other answer you get. Given the number of particles in the universe is estimated to be 10^80, 100^283 combinations would be impossible to print on paper.

Or else I’ve gotten something wrong. If so, please clue me in.

Answer 8

Your code does not match your problem statement and it is therefore unclear how to proceed.

You say that the data list contains negative values and contains duplicates. You give an example which does both. In fact, the values are limited to non-zero integers in the range [-200,200] but the data list is at least 2,000 and typically 10,000 or more, so there would have to be duplicates.

Let’s review your “basic logic”:

 for (int c = 100; c >= 0; c--) { if (c * x_k == current.sum) { //if result is correct then save solutions.add(new Context(0, 0, newcoeff)); continue; } else if (current.k > 0) { // recurse with next data element contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff)); } } 

Elsewhere you state that the data must be sorted in numerical order and you start from the tail of the list, k = n -1 (because of zero indexing), so you start with the biggest ones first. The then clause terminates the recursion. While this may be fine in the problem you are solving, it is not the problem you are describing, because it ignores all the combinations of lesser data values that sum to zero.

On the other hand, all the combinations of greater values that sum to zero would be included.

Let’s look, for example, at the last item on your example list, 156, with target sum 5000.

156 * 100 = 15600 so it will not match the target sum until you get into the negative numbers. Of course

 (100 * -100) + (100 * -6) + (100 * 156) = 5000 

and this combination works. (Your sample data set does not include a -100, but it does have two -40s and a -20, so if you want to be true to the data set combine them instead. I’m using -100 to keep the example simple and because you say the data set could include -100.)

But of course

 (100 * -100) + (100 * -6) + (c * -1) + (c * 1) + (100 * 156) = 5000 

for any c, so you will have 100 combinations like this in the output (1 <= c <= 100). But you have 50 in the data set. When you get to 100 * 50 = 5000 you terminate the recursion, so you will never get

 (c * -1) + (c * 1) + (100 * 50) = 5000 

So either your code or your problem statement is buggy. Probably both, because even without considering the coefficients, 10,000 items taken 60 at a time yields on the order of 10^158 combinations, but aside from this premature termination of recursion, I see nothing that would prevent you from having to test the value of the sum of all those combinations, and even if there were zero cost in computing the values, you could not do that many comparisons.

Answer 9

I may be wrong but could this be viewed as a integer partition (was Triangle number, but I remembered I misremembered ) problem?

If that’s the case, each entry would have a membership to a set of results for a given sum. Precalculating and caching the membership results for a given sum (yes a huge table) could form a very quick solution.

I could probably do it, but I’d need a large data set. Interesting though…

Consult the guru Knuth http://cs.utsa.edu/~wagner/knuth/fasc3b.pdf