javascript-查找在特定限制下给出最大和的子集（子集和）

Question

我有一个包含一些整数值的数组，我需要得到其中的一个子集，它给我的最大和小于给定值
假设我有一个数组：

[40, 138, 29, 450]

我想得到这个数组的一个子集，最大化总和，但低于用户给定的限制，比如250。在这种情况下，它应该返回[139,40,29]<我看了一下这个问题和相关的答案，并尝试使用给出的代码，但我不太理解。无论如何，我已经尝试过了，将最小值设置为0，将最大值设置为给定的限制，但它总是返回“5”，这是不正确的，因为限制值大约为300，数组中的数字都超过50<我找不到任何可以帮助我的东西，所以我想问是否有人可以给我一些代码或伪代码来理解如何做到这一点。

Answer 1

这是一个蛮力解决方案。首先，我们从原始数组中获得所有可能的值组合，取它们的总和，看看哪一个能在不溢出给定最大值的情况下得到最高值。

var ary = [40, 138, 29, 450];

// Function to construct a power set. A power set is just the set of
// all possible subsets of some given set.
function makePowerSet(ary) {
    powerSet = [];
    for (let ps = 1; ps <= Math.pow(2, ary.length); ps++) {
        subset = [];
        for (let i = 0; i < ary.length; i++) {
            if (ps & Math.pow(2, i)) subset.push(ary[i]);
        }
        powerSet.push(subset);
    }
    return powerSet;
}

// Function to calculate the sum of an array.
function getSum(ary) {
   return ary.reduce((sum, cur) => {
      return sum + cur;
   }, 0);
}

function getSubsetBelow(val, ary) {
    let bestSoFar;
    let bestSoFarSum = 0;
    for (let subset of makePowerSet(ary)) {
        const sum = getSum(subset);
        if (sum > val) continue;
        if (sum > bestSoFarSum) {
            bestSoFar = subset;
            bestSoFarSum = sum;
        }
    }
    
    console.log("Got a best sum value of", bestSoFarSum, "with the subset", bestSoFar);
}

getSubsetBelow(250, ary)

Answer 2

快速紧凑的解决方案：

function maxSum(input, limit) {
    const sums = {};
    let max = 0;

    const collectSums = (n, i, values) => {
        for (; i < input.length; i++) {
            const sum = n + input[i];
            if (sum <= limit) {
                values.push(input[i]);
                if (sum >= max && values.length > 1) {
                    max = sum;
                    sums[max] = values.slice(); // https://jsperf.com/copying-an-array
                }
                collectSums(sum, i + 1, values);
            }
        }
        values.pop();
    };

    collectSums(0, 0, []);

    return sums[max] || [];
}

除了输入的必要迭代之外，这个解决方案试图通过不使用昂贵的数组操作来保持低复杂度。只需要复制找到的子集来跟踪可能的组合。尽管如此，可能还有更聪明的解决方案来提高性能。

该方法将返回最后找到的组合，这意味着两个具有不同顺序的相同值的输入列表可能会产生不同的结果：

maxSum([1, 4, 200, 5], 205) == [200, 5];
maxSum([5, 200, 1, 4], 205) == [200, 1, 4];

如果需要所有可能的组合，请替换此行：

sums[max] = values.slice(); // https://jsperf.com/copying-an-array

与此：

sums[max] = sums[max] || [];
sums[max].push(values.slice());

然后返回所有组合：

maxSum([1, 4, 200, 5], 205) == [[1, 4, 200], [200, 5]];

但请注意，这将始终返回数组数组，即使只有一种可能性：

maxSum([40, 138, 29, 450], 250) == [[40, 138, 29]];

Answer 3

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

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

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