是否有任何“技巧”可以加快对大型背包组合式问题的采样速度？

小编典典

是否有任何“技巧”可以加快对大型背包组合式问题的采样速度？

algorithm

更新：我已经意识到，由于涉及大量数据（15k项以上），因此无法以当前形式回答以下问题。
我刚刚发现，我要帮助的小组只允许其运行一个月，然后终止该小组以使用结果（这就是为什么他们希望在更快的时间内获得更多结果）。这对我来说似乎很疯狂，因为它们仅使用前几组数据（大列表中的最后一项永远不会使用）。因此，我正在修订此问题，以获取预期输出的样本（解决方案的近似值而不是完整的解决方案）。在更短的时间内完成此操作的最佳方法是什么？他们似乎想要多样化的结果样本，是遗传算法起作用还是某种抽样技术？其余问题保持不变（相同的输入/输出），但我

我的问题不完全是背包问题，而是非常接近的问题。基本上，我正在尝试查找等于特定值的X个项目的每种组合。我从一个我的朋友那里听说过这个问题，他在一个小型学校研究实验室工作，该过程运行了大约25天才能完成。看起来真的很可怕，所以我提供了帮助（对我来说是好处，是我可以学习和帮助一些非常好的人），所以我想出了如何通过多线程对其进行扩展（我将在下面的代码中提供），减少了几天的处理时间，但我仍然不满意，所以我只是将代码移植到GPU上工作，但我感到不满意（尽管他们很高兴，因为它速度更快，我捐赠了我的旧显卡），因为我只是在利用硬件，而不是在利用任何算法。马上，

因此，在这种背景下，我可以做些什么来通过算法加快速度吗？我的直觉告诉我没有，因为既然他们需要每种组合，从逻辑上看，计算机必须处理每种组合（数十亿），但是我之前在这里已经看到了令人惊奇的事情，即使很小的提速也可以在几天的处理中有所作为。

我喜欢超过10个版本的代码，但这是一个使用多线程的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<Context> solutions;

    static {
        final int numberOfThreads = 2;
        executor =
            new ThreadPoolExecutor(numberOfThreads, numberOfThreads, 1000, TimeUnit.SECONDS,
                                   new LinkedBlockingDeque<Runnable>());
        // concurrent because of multi-threaded insertions
        solutions = new ConcurrentLinkedQueue<Context>();
    }


    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 <= 100; c++) {
            coeff[k] = c;
            int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
            if (c * x_k == sum) {
                //printResult(newcoeff);
                solutions.add(new Context(0, 0, newcoeff));
                continue;
            } else if (k > 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<Void> {
        // queue with contexts to process
        private Queue<Context> contexts;

        ComputePartialSum(Context request) {
            contexts = new ArrayDeque<Context>();
            contexts.add(request);
        }

        public Void call() {
            while(!contexts.isEmpty()) {
                Context current = contexts.poll();
                int x_k = data[current.k];
                for (int c = 0; c <= 100; c++) {
                    current.coeff[current.k] = c;
                    int[] newcoeff = Arrays.copyOf(current.coeff, current.coeff.length);
                    if (c * x_k == current.sum) {
                        //printResult(newcoeff);
                        solutions.add(new Context(0, 0, newcoeff));
                        continue;
                    } else if (current.k > 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：我认为问题本身很容易/很常见，但是问题正在大规模运行，所以这是我进行测试时获得的真实数据（虽然不大，但大约有3000项，因此如果要测试您不必自己生成它）：

private static final int target_sum = 5 * 1000;
private static final List<Integer> 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个变量的蛮力将使我确信，在更大的数据上它将更快。我不是想熄灭灯火，而是在寻找可以提供甚至更快的结果的小改进（或更大的设计改进）（我将研究每个建议）。另外，如果有任何需要放松的假设，请告诉我。

谢谢！

阅读 257

2020-07-28

共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]);

    }
}

2020-07-28