javascript - 找到在一定限制下给出最大总和的子集(子集总和)

Question

我有一个包含一些整数值的数组，我需要得到它们的一个子集，它给出低于给定值的最大总和。
假设我有这个数组:

[40, 138, 29, 450]

我想得到这个数组的一个子集，使总和最大化但低于用户给定的限制，比方说 250。在这种情况下，它应该返回 [139, 40, 29]。
我看了看 this问题和相关答案，并尝试使用给出的代码，但我不是很了解。不管怎样，我试过了，将最小值设置为 0，将最大值设置为给定的限制，但它一直返回我不正确的“5”，因为限制就像 300，而我数组中的数字都超过了 50。
我找不到任何可以帮助我的东西，所以我想问是否有人可以给我一些代码或伪代码来了解如何执行此操作。

Answer 1

基本上，您可以将索引处的元素添加到临时数组中，也可以不添加。然后检查索引是否达到数组的长度或者总和是否大于想要的总和，然后检查总和并将临时数组添加到结果集中，或者不。

继续，直到访问完所有索引。

function getCombinations(array, sum) {
    function add(a, b) { return a + b; }

    function fork(i, t) {
        var r = (result[0] || []).reduce(add, 0),
            s = t.reduce(add, 0);
        if (i === array.length || s > sum) {
            if (s <= sum && t.length && r <= s) {
                if (r < s) {
                    result = [];
                }
                result.push(t);
            }
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

console.log(getCombinations([40, 138, 29, 450], 250));

.as-console-wrapper { max-height: 100% !important; top: 0; }