javascript - 查找低于/等于给定限制的最高总和

Question

我有以下功能:

var object = [12,23,14,35,24];
//debugger;
function f(objects, sum){
  var curSum = objects[0];
  var maxSum = 0;
  var start = 0;
  for (var i = 1; i < objects.length; i++) {
    while(curSum > sum && start < i){
      curSum -= objects[start];
      start++
    }
    maxSum = Math.max(maxSum, curSum);
    curSum += objects[i];
    if(curSum <= sum){
      maxSum = Math.max(curSum, maxSum);
    }
  }
  return maxSum;
}

console.log(f(object,50));

由于元素 12,14,24

，我希望最大可能的总和为 50

但是，我只能设法达到 49。我在这里缺少什么？

Answer 1

您可以通过迭代数组并检查临时数组是否具有正确的总和来采用递归方法，并检查结果是否替换为更小的总和或推送到相同的总和部分。

function combine(array, sum) {
    function fork(i, p) {
        var s = p.reduce((a, b) => a + b, 0),
            l = (result[0] || []).reduce((a, b) => a + b, 0);

        if (i === array.length) {
            if (s <= sum) {
                if (l < s) {
                    result = [p];
                }
                if (l === s) {
                    result.push(p);
                }
            }
            return;
        }
        fork(i + 1, p.concat(array[i]));
        fork(i + 1, p);
    }
    var result = [];
    fork(0, []);
    return result;
}

console.log(combine([12, 23, 14, 35, 24], 50));

.as-console-wrapper { max-height: 100% !important; top: 0; }