NN小于或等于的预定义数字的最佳可能组合总和

Question

我有一个管道长度列表,我需要在最大允许长度内安装这些长度,以获得最佳产量

例如,最大允许长度为90,我需要制作的部分是:

25,60,13,48,23,29,27,22

为了在90岁以内最合适,我会有一组这些数字:

60,29(共89个)

27,25,13,​​23(共88个)

48,22(共70个)

我发现这个答案类似的问题,但我不知道如何将它转换到Excel中使用或JavaScript或PHP

任何帮助,将不胜感激.

谢谢.

Answer 1

这是一种可能的解决方案。但它是一种强力算法，因此它的速度不是尽可能快。

function bestComb(nums, target) {
  var combinations = [];
  var sums = [];
  function loop(idx, comb, sum) {
    if(idx >= nums.length || sum + nums[idx] > target) {
      combinations.push(comb.slice());
      sums.push(sum);
      return;
    }
    for(var i = idx; i < nums.length; i++) {
      if(sum + nums[i] > target) break;
      if(sum + nums[i] === target) {
        combinations.push(comb.slice());
        combinations[combinations.length - 1].push(nums[i]);
        sums.push(sum + nums[i]);
        break;
      }
      comb.push(nums[i]);
      loop(i + 1, comb, sum + nums[i]);
      comb.pop();
    }
  }

  nums = nums.slice();
  nums.sort(function(a,b) {return a - b});
  loop(0, [], 0);

  if(sums.length === 0) return null;
  var maxSum = sums[0],
      maxComb = combinations[0];
  for(var i = 1; i < sums.length; i++) {
    if(sums[i] > maxSum || sums[i] === maxSum && combinations[i].length < maxComb.length) {
      maxSum = sums[i];
      maxComb = combinations[i];
    }
  }

  return maxComb;
}

var nums = [25, 60, 13, 48, 23, 29, 27, 22];

var solution = bestComb(nums, 90);

console.log(solution);