javascript

Question

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

[40, 138, 29, 450]

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

Answer 2

这是一个蛮力解决方案。首先，我们从原始数组中获取所有可能的值组合，取它们的总和，然后查看其中哪一个为我们提供了最高值而不溢出给定的最大值。

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 的简单方法）。

Answer 3

快速紧凑的解决方案：

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

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

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

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());

所有组合然后 returned:

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

但请注意，这总是 return 一个数组的数组，即使只有一种可能性：

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

Answer 4

#求数组元素紧凑子序列的最大和

import sys
def solution(A):
 max_ending = max_slice = -sys.maxsize
 if(len(A)==1):
     return A[0]
 else:
     for a in A:
         max_ending =max(a,max_ending + a)
         max_slice = max(max_slice, max_ending)
     return max_slice

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

javascript - find subset that gives maximum sum under a certain limit (subset sum )

algorithm

subset-sum