Логическая форма, получающая минимальное значение UpperBound для данного номера из набора чисел

Question

Моя проблема заключается в следующем

У меня есть несколько номеров, как показано ниже:

  2
  2
  2
  2
  3
  3
 17
 17
 17
 17
 17
 17
 17
 17
 17
 34
 34
 34
 34
 34
 68
 68
 68
136

Поэтому, если в качестве входных данных я приведу следующее число, результат должен быть следующим:

[вывод - сумма заданного числа, которое просто больше, чем ввод]

 Input  Output
     3      2,2
     4      2,2
     254    17,34,68,136
     7      2,3,3 [or also with 2,2,2,2 but if return same sum,
                   then number count should min]
     205    2,68,136
     10     2,2,3,3

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

Благодарю.

Answer 1

Я нашел возможную отправную точку в Википедии:

Более общая проблема требует суммирования подмножества с указанным значением (не обязательно 0). Это может быть решено простой модификацией алгоритма выше. Для случая, когда каждая xi положительна и ограничена одной и той же константой, Пизингер нашел линейный алгоритм времени.[3]

Ваша основная проблема выглядит как расширенная версия этого. Вам нужно найти подмножество вашего набора суммирования для input - или провалившись, суммируя input+1или не получится, суммируя input+2, так далее.

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