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

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

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

  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

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

Спасибо.


sum algorithm knapsack-problem minimum upperbound
person Manu Batham    schedule 04.05.2011    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

person Robin Green    schedule 04.05.2011