покрыть большее число, с выбором заданных меньших чисел

Question

У меня есть массив чисел (например, [2, 4, 5, 7]), и я должен найти наилучшую возможную комбинацию, чтобы «покрыть» большее число, «крышка» означает здесь, что сумма выбранных чисел должна быть по крайней мере равным большему числу. Сумма выбора должна быть как можно ближе к большему числу, и в случае 2+ возможных оптимальных выборов следует выбирать тот, который использует меньше чисел в своей сумме, если еще есть 2+ возможных варианта, один чьи выбранные номера идут дальше перед массивом, должны быть возвращены. Число нельзя использовать дважды, если только оно не появляется дважды в данном массиве.
пример:

[2, 4, 5, 7], to cover 10 => [4,7] since 11 is the closest to 10 (and at least 10) possible

[5, 6, 3, 6, 20], to cover 18 => [20], since 20 is the closest to 18 (and at least 18) possible and [20] uses fewer numbers than [5, 6, 3, 6]

Моя проблема в том, что у меня есть древовидная структура данных и я хочу свернуть как можно меньше элементов , позволяя пользователю видеть как можно больше без прокрутки. Вам не нужно ничего кодировать, достаточно просто идеи для алгоритма (хотя моя реализация будет в js).

Заранее спасибо:)

Answer 1

Вы можете сделать это так:

const arr_origin = [2,4,5,7,2,4,5,20];
const arr_unique = [...new Set(arr_origin)];
const cover_num = 10;

var closest_sum = arr_origin.reduce((a,b) => a+b, 0);
var arr_optimal = arr_unique;

find([], 0);

function find(arr_now, idx) {
    const sum = arr_now.reduce((a,b) => a+b, 0);

    if ( (cover_num <= sum && sum < closest_sum) || 
         (cover_num <= sum && sum == closest_sum && arr_now.length < arr_optimal.length) )
    {
        closest_sum = sum;
        arr_optimal = arr_now;
    }

    if (idx < arr_unique.length) {
        // skip this element
        find(arr_now, idx+1);

        // add this element into array
        var arr_new = arr_now.slice(0);
        arr_new.push(arr_unique[idx]);
        find(arr_new, idx+1);
    }
}

Это даст:

// [2, 4, 5, 7], to cover 10 => [4,7], 11
// [5, 6, 3, 6, 20], to cover 18 => [20], 20
// [2,4,5,7,2,4,5,20], to cover 10 => [4,7], 11

Спасибо

Answer 2

При нескольких начальных тестах это решение, похоже, работает:

Пример Repl

const maxValue = (array, targetValue) => {
  array.sort((a, b) => (a < b) ? -1 : 1)
  let sums = []
  for(let i = 0; i < array.length - 1; i++) {
    let addends = []
    let addendX = array[i]
    let currentSum = addendX
    let closest = (currentSum >= targetValue)
      ? true
      : false
    addends.push(addendX)
    for(let j = i + 1; j < array.length; j++) {
      if(closest) break
      let addendY = array[j]
      if(
        !closest &&
        currentSum + addendY >= targetValue
      ) {
        currentSum += addendY
        closest = true
      } else {
        currentSum += addendY
      }
      addends.push(addendY)
    }
    sums.push({
      sum: currentSum,
      addends: addends,
    })
  }
  return sums.sort((a, b) => (a.sum < b.sum) ? -1 : 1)[0]
}
console.log(maxValue([2, 4, 5, 7], 11))
/*
{ sum: 11, addends: [ 2, 4, 5 ] }
*/
console.log(maxValue([5, 6, 3, 6, 20], 18))
/*
{ sum: 20, addends: [ 3, 5, 6, 6 ] }
*/

Возможно, он использует некоторую оптимизацию или может давать неточные результаты, но вы должны будете предоставить мне больше тестов для решения этих проблем.