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

Question

我有一个带有一些整数值的数组,我需要得到它们的一个子集,它给出了一个不如给定值的最大总和.
所以我想说我有这个数组:

[40, 138, 29, 450]

我想得到这个数组的一个子集,它最大化总和但是不如用户给出的限制,比方说250.在这种情况下它应该返回[139,40,29].
我看了这个问题和相关的答案,并尝试使用给出的代码,但我不太了解它.无论如何我已经尝试过,将min设置为0并将max设置为给定的限制,但它不断返回"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; }