Линейный алгоритм для поиска минимальной суммы подмножества через порог
У меня есть коллекция из N натуральных чисел, каждое из которых ограничено (относительно небольшой) константой C. Я хочу найти подмножество этих чисел с наименьшей суммой, большей (или равной) значению K.
Количество участвующих не очень большие (<100), но мне нужны хорошие показатели даже в худшем случае. Я подумал, что, возможно, смогу адаптировать алгоритм динамического программирования Пизингера к задаче; он запускается за время O (NC), и я случайно встретил требования ограниченных положительных чисел.
[Редактировать]: номера не отсортированы и могут быть дубликаты.Однако я недостаточно хорошо понимаю алгоритм, чтобы сделать это сам. На самом деле, я даже не уверен, что предположения, на которых оно основано, остаются в силе …
-Можно ли адаптировать этот алгоритм к моим потребностям?
-Или есть другой линейный алгоритм, который я мог бы использовать так же эффективно?
-Может ли кто-нибудь предоставить псевдокод или подробное объяснение?
Благодарю.
Ссылка на код Subset-Sum, который я исследовал:
Быстрое решение алгоритма суммы подмножеств с помощью Pisinger
(Извините, если это плохо сформулировано / отформатировано / и т. Д. Я все еще новичок в StackOverflow …)
Решение
Алгоритм Пизингера дает вам наибольшую сумму, меньшую или равную вместимости рюкзака. Чтобы решить вашу проблему, используйте Pisinger, чтобы выяснить, что не положить в подмножество. Формально, пусть предметы будут w_1, …, w_n, а минимум — K. Передайте w_1, …, w_n и w_1 + … + w_n — K Пизингеру, а затем возьмите каждый предмет, который Пизингер не делает.
Другие решения
Ну, одно решение состоит в том, чтобы:
T = {0}
for x in V
for t in T
T.insert(x+t)
for i in K to max(T)
if (T.contains(i))
return i
fail
Это дает вам размер подмножества, но вы можете адаптироваться к выводу членов.
Максимальный размер T равен O (N) (из-за границы C), поэтому время выполнения равно O (N ^ 2), а пространство равно O (N). Вы можете использовать битовый массив длины NC в качестве резервного хранилища T.