-2

I need to get the best combination of numbers from the array numbers that are closest to the number max. (addition numbers from array numbers is allowed)

var numbers = [2, 5, 3, 7, 9, 20, 54, 89, 10]; // some numbers in array
var max = 10; // the highest possible number we want to get from array
var highest = [];

In this case, the output should be (3, 7) or (2, 5, 3) or (10), the output should not be 9

I have done this, but this is not what I want.

var possibles = numbers.filter(number => number <= max);
highest.push(Math.max(...possibles));
possibles.sort((a,b) => b - a);
possibles.forEach(number =>{
  if( (max - highest[0]) <= number){
     highest.push(Math.max(...possibles));
  }
});

The output in this case is 9, which is not the highest possible number.

EnelGy
  • 25
  • 1
  • 7

1 Answers1

2

You could take a recursive approach by using some methods to minimize the data and the iteration.

First of all it take a variable to keep an actual minimum sum of all values of a temporary array right.

Another function checks if an array with same value already exists in the result array.

At the end iter performs some checks for exit or adding right to result and finally fork the call to itself by using either the actual value or not.

The result set contains all possible results with the max possible sum.

function getMax(values, max) {
    const
        includes = (arrays, array) => arrays.some(a => a.join() === array.join()),
        iter = ([value, ...left], right = [], sum = 0) => {
            ++count;
            if (sum > max) return;
            if (sum > min) {
                result = [right];
                min = sum;
            } else if (sum === min && !includes(result, right)) {
                result.push(right);
            }
            if (sum === max || value === undefined) return;

            iter(left, [...right, value], sum + value);
            iter(left, [...right], sum);
        };

    let min = 0,
        count = 0,
        result = [];

    iter(values.filter(v => v <= max).sort((a, b) => b - a));
    console.log('iterations', count);
    return result;
}

getMax([2, 5, 3, 7, 9, 20, 54, 89, 10], 10).map(a => console.log(...a));
.as-console-wrapper { max-height: 100% !important; top: 0; }
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
  • Thanks, this helped me a lot, but I have a question. In the case I needed to return only 1 highest possible combination of these numbers (I need to make it faster), what should I change ? – EnelGy Jan 02 '22 at 11:25
  • you still need to iterate until the end, because you do not know in advance which combination gets the maximum. – Nina Scholz Jan 02 '22 at 11:30
  • Ah, okay. So there's probably not any faster way right ? – EnelGy Jan 02 '22 at 11:33
  • 1
    i added soem changes and now `10` is a valid result as well until you want at lest two items in the result array. by sorting descending, the iteration count is the smalest. cou could play with sorting and have a look to count. – Nina Scholz Jan 02 '22 at 12:36