javascript - 查找在特定限制下给出最大总和的子集（子集和） [英] javascript - find subset that gives maximum sum under a certain limit (subset sum )

问题描述

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

所以让我说我有这个数组：

I have an array with some integer values, and I need to get a subset of them that gives me the maximum sum that is inferior to a given value.
So let's say I have this array:

[40, 138, 29, 450]

我想得到这个数组的一个子集，它最大化总和但是不如用户给出的限制，比方说250.在这种情况下它应该返回[139， 40,29]。

我看过这个问题和相关答案，并试图使用给出的代码，但我不太了解它。无论如何我已经尝试过，将min设置为0并将max设置为给定的限制，但它不断返回5，这是不正确的，因为限制为300，我的数组中的数字都超过50。

我找不到任何可以帮助我的东西，所以我问是否有人可以给我一些代码或伪代码来理解如何做到这一点。

I would like to get a subset of this array that maximize the sum but is inferior to a limit given by the user, let's say 250. In this case it should return [139, 40, 29].
I had a look at this question and related answer, and tried to use the code given, but I didn't understand it very well. Anyway I've tried it, setting the min to 0 and the max to the limit given, but it keeps returning me "5" that is not correct, since the limit is like 300 and the numbers in my array are all over 50.
I couldn't find anything that could help me, so I'm asking if anyone could give me some code or pseudocode to understand how to do this.

推荐答案

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

Basically you could either add the element at the index to a temporary array or not. Then check if the index reaches the lenght of the array or if the sum is greater than the wanted sum, then either check the sum and add the temp array to the result set, or not.

继续访问所有索引。

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

这篇关于javascript - 查找在特定限制下给出最大总和的子集（子集和）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！