Существует ли алгоритм, который, учитывая список целых чисел, возвращает список целых чисел размера N, где общее значение равно V ± 100?

Question

Учитывая список целых чисел, как я могу вернуть список целых чисел размера N , где общая сумма целых чисел равна V ± 100 ?

Например, если у меня есть список целых чисел list = [652, 840, 585, 147, 652, 576, 786, 362, 800, 591], как я могу вернуть список целых чисел размер 21 с общим значением от 11500 до 11700 как V = 11,600 и N = 21 ? И в этом случае было бы нормально повторить целое число более одного раза.

Я попытался немного погуглить, но не смог найти то, что искал.

Я бы предпочел решение в JavaScript, но любой язык подойдет.

Answer 1

Идея решения этой проблемы аналогична программному решению Dynami c для задачи Subset Sum .

Я не буду давать вам код. Но я дам вам точный подход.

«в пределах 100» - отвлекающий маневр. Лучше просто выбрать «самое близкое». Затем проверьте, получили ли вы ответ в пределах 100 от цели. (Как это бывает, в этом случае вы можете попасть в целевую сумму по носу.)

Идея состоит в том, что для n в 0..N вы хотите построить значения отображения структуры данных, которые вы можете получить с целыми числами n в путь, по которому вы могли попасть туда. Для n=0 это просто - ваша структура данных всего {0: null}. (Вы можете получить 0 с пустой суммой.)

Для n=1 вы получите структуру данных с такими записями, как 840: [840, [null]].

Для n=2 вы получите со структурой данных с такими записями, как 1680: [840, [840, [null]]].

Когда вы достигнете n=21, вы можете извлечь ближайшее решение с помощью:

let bestValue = null;
Object.keys(solution).forEach(function (value) {
    if (bestValue == null) {
        bestValue = value*1; // The *1 casts a string to a number.
    }
    else if (Math.abs(targetSum - value) < Math.abs(targetSum - bestValue)) {
        bestValue = value*1;
    }
});

let bestSolution = solution[bestValue];

// We have the bestSolution as a linked list.  Recover it as an array.
let answer = [];
while (bestSolution) {
    answer.push(bestSolution[0]);
    bestSolution = bestSolution[1];
}

В вашем конкретном c решении окончательный ответ будет примерно таким:

[
  147, 147, 147, 147, 147,
  147, 147, 147, 652, 652,
  800, 800, 800, 840, 840,
  840, 840, 840, 840, 840,
  840
]