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

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 и т. Д.

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