我有一个包含一些整数值的数组，我需要获取它们的子集，该子集给出小于给定值的最大总和。
假设我有这个数组：
[40, 138, 29, 450]
我想获得该数组的一个子集，使总和最大化，但低于用户给出的限制，比如说 250。在这种情况下，它应该返回 [139, 40, 29]。
我看了一下this https://stackoverflow.com/questions/12807855/algorithm-extract-subset-based-on-property-sum问题和相关答案，并尝试使用给出的代码，但我不太理解它。不管怎样，我已经尝试过了，将最小值设置为 0，将最大值设置为给定的限制，但它总是返回给我“5”，这是不正确的，因为限制大约是 300，而我的数组中的数字都超过 50。
我找不到任何可以帮助我的东西，所以我问是否有人可以给我一些代码或伪代码来了解如何做到这一点。
基本上，您可以将索引处的元素添加到临时数组中，也可以不添加。然后检查索引是否达到数组的长度，或者总和是否大于所需的总和，然后检查总和并将临时数组添加到结果集中，或者不检查总和。
继续下去，直到访问完所有索引。
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; }
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
