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

Question

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

[40, 138, 29, 450]

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

Answer 1

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

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

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

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

这是一个强力解决方案。首先，我们从原始数组中获取每个可能的值组合，获取它们的总和，并查看哪些值得到我们最高值而不会溢出给定的最大值。

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)

这看起来非常类似于knapsack problem，它是NP难的，所以我不知道你是否能够找到一个有效的算法。但是，对于我在这里所写的内容，肯定会有一些优化，例如，阵列中任何已超过限制的元素都不能成为解决方案的一部分（简单的方法可以消除450）。