How to get the best combination of numbers from the array of numbers that are closest to the number-CodePudding

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.

CodePudding user response：

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