javascript - 背包 - 从总值(value)中确定集合

Question

看到this之后讲座我创建了以下背包代码。在讲座中，教授说从最优值(19:00 分钟)确定集合很容易，但我找不到如何去做。我在代码中提供了一个将值相加为 21 的示例，我如何根据该值确定集合(在本例中为 12、7、2)？

/*
    v = value
    w = weight
    c = capacity
 */
function knapsack(v, w, c) {
    var n = v.length,
        table = [];
    // create two-dimensional array to hold values in memory
    while (table.length <= c) {
        table.push([]);
    }

    return ks(c, 0);
    function ks(c, i) {
        if (i >= n) {
            table[c][i] = 0;
            return table[c][i];
        }
        if (c < w[i]) {
            if (table[c][i+1] === undefined) {
                table[c][i + 1] = ks(c, i + 1);
            }
            return table[c][i + 1];
        }
        else {
            if (table[c][i + 1] === undefined) {
                table[c][i + 1] = ks(c, i + 1);
            }
            if (table[c - w[i]][i + 1] === undefined) {
                table[c - w[i]][i + 1] = ks(c - w[i], i + 1);
            }
            return Math.max(table[c][i + 1], v[i] + table[c - w[i]][i + 1]);
        }
    }
}

//This is a test case
var v = [7, 2, 1, 6, 12];
var w = [3, 1, 2, 4, 6];
var c = 10;
var result = knapsack(v, w, c);
document.getElementById("solution").innerHTML = result;

<pre>Optimal solution value is: <span id="solution"></span></pre>

Answer 1

这一点都不容易。确定某组数字的子集是否具有特定总和称为 subset sum problem。 ，它是 NP 完全的，就像背包本身一样。只保留指向子问题的解决方案的指针会容易得多，您从中构建了更大子问题的最佳解决方案。这样你就可以沿着全局最优解的指针返回，找到给你最优值的实际集合。

(编辑:如 j_random_hacker 的评论所述，一旦我们有了 DP 表，我们实际上可以确定在 O(n²) 时间内给出最佳值的集合，方法是最佳解决方案并通过表向后工作，考虑可能是最后添加的项目的每个可能项目，并检查该解决方案是否与预期值匹配。)

另一方面，我建议您观看一些不同的讲座。这家伙提出了一些奇怪的说法，比如 O(nc)——n 个项目，c 容量——比 O(2ⁿ) 小得多，当 c 很大时，这是不正确的. (事实上​​ ，这称为 pseudo-polynomial time 解决方案，它仍然是输入长度的指数，以位为单位。)