Best possible combination sum of predefined numbers that smaller or equal NN

Question

I have a list of lengths for pipes and I need fit these lengths within maximum allowed length for the best yield

For example the max allowed length is 90 and the pieces I need to make are:

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

For the best fit within 90 I'd have a group of these numbers:

60, 29 (89 total)

27, 25, 13, 23 (88 total)

48, 22 (70 total)

I found this answer to similar question, but I don't know how to convert it to use in excel or javascript or php

Any help would be appreciated.

Thank you.

Answer 1

Here is one possible solution. But it is a brute force algorithm so it's not as fast as possible.

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