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

debugcn 发表于 Dev

彼德

假设我有一个列表[1,2,3,4,5,6,7]，我想找到最接近给定数字的数字总和。对不起的解释很抱歉，但是这里有一个例子：

假设我有一个列表[1,2,3,4,5,6,7]我想找到最接近的数字，例如10。

然后该方法应返回6和4或7和3，因为它最接近他可以得到10。所以5 + 4将是错误的，因为那是9并且他可以得出10。

另一个示例：您想要最接近14的那个，那么他应该返回7和6

如果您有任何疑问，请PLZ询问，因为它很难解释我想要的内容：P

Sabithpocker

对于函数combine，locationOf中，从不同的答案采取不同的作者写的。

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