javascript - Finding closest sum of numbers to a given number - Stack Overflow

admin管理员组

文章数量:1316834

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

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

• javascript
• php

Share Improve this question Follow asked Apr 1, 2016 at 11:04 PeterPeter 7311 silver badge99 bronze badges 11

• 4 How many times can you use any item from the array? For example: if the given number is 10, then you can get a sum of ten times 1 to get to 10. Also: this looks like a school question. – klaar Commented Apr 1, 2016 at 11:06
• What you have tried so far? – Manwal Commented Apr 1, 2016 at 11:09
• 1 would 2+3+5 be allowed? – messerbill Commented Apr 1, 2016 at 11:10
• @peter Can you add some more details to your question? Its quite confusing. – Rajaprabhu Aravindasamy Commented Apr 1, 2016 at 11:16
• what if the input number is 28 ? – RomanPerekhrest Commented Apr 1, 2016 at 12:13

 |  Show 6 more ments

5 Answers 5

Sorted by: Reset to default 2

Functions for bine, 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 binations = bine(array); //get all binations
  binations = limit ? binations.filter(checkLength) : binations;//limit length if required
  var sum = binations.map(function(c) { //create an array with sum of binations
    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 bination

  console.log(sum, binations, index);

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


function bine(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>

 var data= [1, 2, 3,4,5,6,7];
  var closest = 14;
 for (var x = 0; x < data.length; x++) {
    for (var y = x+1; y < data.length; y++) {
             if(data[x] + data[y] == closet){
                     alert(data[x].toString() + "  " + data[y].toString());
                }
            }
       }

From what I understood from your question, I made this snippet. I assumed you did not wanted to have the same digit twice (e.g 14 => 7 + 7).

It is working with your examples.

var arr = [1, 2, 3, 4, 5, 6, 7];

var a = 0, b = 0;
var nb = 14;

for(var i in arr) {
  for(var j in arr) {
    if(i != j) {
      var tmp = arr[i] + arr[j];
      if(tmp <= nb && tmp > a + b) {
        a = arr[i];
        b = arr[j];
      }
    }
  }
}

document.write("Closest to " + nb + " => " + a + " + " + b);

I have a little bit long winded solution to the problem just so it is easier to see what is done.

The main benefits with solution below:

• The second loop will not start from beginning of the array again. What I mean that instead of having loop_boundary for second loop as 0 as you normally would, here it starts from next index. This helps if your numbers array is long. However, if it as short as in example, the impact in performance is minimal. Decreasing first loop's boundary by one will prevent errors from happening.
• Works even when the wanted number is 1 or negative numbers.

Fiddle:

JSFiddle

The code:

var numbers = [1,2,3,4,5,6,7];
var wanted_number = 1;
var closest_range, closest1, closest2 = null;

var loop1_boundary = numbers.length-1;
for(var i=0; i<loop1_boundary; i++) {

    var start_index = i+1;
    var loop2_boundary = numbers.length;

    for(var k=start_index; k<loop2_boundary; k++) {

        var number1 = parseInt(numbers[i]);
        var number2 = parseInt(numbers[k]);

        var sum = number1 + number2;
        var range = wanted_number - sum;

        document.write( number1+' + '+number2 +' < '+closest_range+'<br/>' );

        if(Math.abs(range) < Math.abs(closest_range) || closest_range == null ) {
            closest_range = range;
            closest1 = number1;
            closest2 = number2;
        }

    }

    if(range==0){
        break;
    }
}

document.write( 'closest to given number was '+closest1+' and '+closest2+'. The range from wanted number is '+closest_range );

This proposal generates all possible binations, collects them in an object which takes the sum as key and filters then the closest sum to the given value.

function getSum(array, sum) {
    function add(a, b) { return a + b; }

    function c(left, right) {
        var s = right.reduce(add, 0);
        if (s > sum) {
            return;
        }
        if (!result.length || s === result[0].reduce(add, 0)) {
            result.push(right);
        } else if (s > result[0].reduce(add, 0)) {
            result = [right];
        }
        left.forEach(function (a, i) {
            var x = left.slice();
            x.splice(i);
            c(left.slice(0, i), [a].concat(right));
        });
    }

    var result = [];
    c(array, [], 0);
    return result;
}

function print(o) {
    document.write('<pre>' + JSON.stringify(o, 0, 4) + '</pre>');
}

print(getSum([1, 2, 3, 4, 5, 6, 7], 10));
print(getSum([1, 2, 3, 4, 5, 6, 7], 14));
print(getSum([1, 2, 3, 4, 5, 6, 7], 19));

本文标签： javascriptFinding closest sum of numbers to a given numberStack Overflow