查找给定数字的最接近的数字总和

Question

Say I have a list [1,2,3,4,5,6,7] and I would like to find the closest sum of numbers to a given number. Sorry for the crappy explanation but here's an example:

Say I have a list [1,2,3,4,5,6,7] I want to find the closest numbers to, say, 10.

Then the method should return 6 and 4 or 7 and 3 because its the closest he can get to 10. So 5 + 4 would be wrong because thats 9 and he can make a 10.

another example : you want the closest to 14 , so then he should return 7 and 6

If you got any questions plz ask because its difficult to explain what I want :P

Answer 1

Functions for combine, locationOf, are taken from different answers, written by different authors.

printClosest([0.5,2,4] , 5);
printClosest([1, 2, 3, 4, 5, 6, 7], 28);
printClosest([1, 2, 3, 4, 5, 6, 7], 10.9);
printClosest([1, 2, 3, 4, 5, 6, 7], 10, 2);
printClosest([1, 2, 3, 4, 5, 6, 7], 10, 3);
printClosest([1, 2, 3, 4, 5, 6, 7], 14, 2);

function printClosest(array, value, limit) {
  var checkLength = function(array) {
    return array.length === limit;
  };
  var combinations = combine(array); //get all combinations
  combinations = limit ? combinations.filter(checkLength) : combinations;//limit length if required
  var sum = combinations.map(function(c) { //create an array with sum of combinations
    return c.reduce(function(p, c) {
      return p + c;
    }, 0)
  });
  var sumSorted = sum.slice(0).sort(function(a, b) {//sort sum array
    return a - b;
  });

  index = locationOf(value, sumSorted);//find where the value fits in
  //index = (Math.abs(value - sum[index]) <= Math.abs(value - sum[index + 1])) ? index : index + 1;
  index = index >= sum.length ? sum.length - 1 : index;
  index = sum.indexOf(sumSorted[index]);//get the respective combination

  console.log(sum, combinations, index);

  document.getElementById("result").innerHTML += "value : " + value + " combi: " + combinations[index].toString() + " (limit : " + (limit || "none") + ")<br>";
}


function combine(a) {
  var fn = function(n, src, got, all) {
    if (n == 0) {
      if (got.length > 0) {
        all[all.length] = got;
      }
      return;
    }
    for (var j = 0; j < src.length; j++) {
      fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
    }
    return;
  }
  var all = [];
  for (var i = 0; i < a.length; i++) {
    fn(i, a, [], all);
  }
  all.push(a);
  return all;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end - start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

<pre id="result"><pre>

</div>