carb0nshel1 carb0nshel1 - 1 month ago 7
Javascript Question

How to find the lowest possible combination of keys within an array

I have an array that will always have 6 keys:

var ary = [5,10,28,50,56,280]
.
I have a variable defined as
limit
I want to check it against.

I want to find the lowest possible combination or sum of keys from this array above
limit
. We'll call this
result
.

A bit of constraints I am trying to work within:

1
result
can be a single key itself:
Such as If
limit = 0
the lowest possible combination or sum of keys should default to the lowest key it can find which would be
ary[ 0 ]
in this case or
5
.

2
result
can be a combination of any keys:
If
limit = 11
,
result
would =
ary[ 0 ] + ary[ 1 ]
( 5 + 10 ). which would be
15
.

3 And lastly,
result
can be above the greatest sum of
ary
:
result = 5 + 10 + 28 + 50 + 56 + 280; // equals 429
In this case limit would just add the minimum value to be just above limit, which would be
ary[ 0 ]
( 5 ). so 5 + 429. Limit would = 434

My attempts in progress:



var ary = [5,10,28,50,56,280];
var limit = 11;

for( var i = 0; i < ary.length; i++ ){
if( ary[ i ] > limit ){
document.write(ary[ i ]);
break;
}
}




Answer
  • Sort the array
  • Do a while loop until the total exceeds the result
  • Inside the while loop add all the components in the array until it exceeds the total

function calcSumOfLowestComponents(ary,limit){
  ary.sort(function(a,b) {
    return a - b;
  });

  var components = [];
  var currentTotal = 0;
  while (currentTotal <= limit){
    for( var i = 0; i < ary.length; i++ ){
      currentTotal += ary[ i ];
      components.push(ary[ i ]);
      if( ary[ i ] + currentTotal > limit ){
         break;
      }
    }
  }
  return { total : currentTotal, components : components};
}

var array = [5,10,28,50,56,280];
document.write("Total = " + calcSumOfLowestComponents(array,2).total + " Components " + calcSumOfLowestComponents(array,2).components + "</br>");
document.write("Total = " + calcSumOfLowestComponents(array,11).total + " Components " + calcSumOfLowestComponents(array,11).components + "</br>");
document.write("Total = " + calcSumOfLowestComponents(array,28).total + " Components " + calcSumOfLowestComponents(array,28).components + "</br>");
document.write("Total = " + calcSumOfLowestComponents(array,429).total + " Components " + calcSumOfLowestComponents(array,429).components + "</br>");

Result

Total = 5 Components 5
Total = 15 Components 5,10
Total = 43 Components 5,10,28
Total = 434 Components 5,10,28,50,56,280,5
Comments