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

Question

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

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

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

为了在 90 以内得到最佳拟合，我有一组这样的数字:

60、29(共 89)

27、25、13、23(共 88 个)

48、22(共 70)

我找到了 this回答类似的问题，但我不知道如何将其转换为在 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);