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

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

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

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