Подбор чисел из списка, которые в сумме дают нужное число #493003

Иногда сталкиваюсь с задачей определить, из каких документов состоит определенная сумма. Задача в том, чтобы из конечного множества чисел выбрать подмножество их, в сумме равное нужному числу. Както давно нашел алгоритм в старой книжечке по программированию, буквально из 15 строчек, но реализация потерялась( Кто-нибудь делал такое? Поделитесь, если есть..

у гугла спросить о задачках о рюкзаке или ранце

Первое, что тна ум приходит что-то в этом роде: (S - искомая сумма, i - элементы сумм). Для i=1 по КоличествоЭлементов Цикл T = i1 + i(следующее); Если S = T Тогда    Записываем составные части Т куда-нить в таблицу; КонецЕсли; КонецЦикла; Потом этот же цикл, но начать с i2.

Но наверняка есть что-нибудь поизящнее)

А если надо выкинуть 3 элемент для оптимальности?

3-й элемент - это какой?

спасибо

тока алгоритм Жадный алгоритм имеет сложность O(n log(n)), и гарантирует нахождение решения, не хуже чем в два раза от оптимального. Алгоритмы динамического программирования для задачи о рюкзаке дают точное решение за время O(nf*) или O(nB). Если величины f* и B не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты), то эти псевдополиномиальные алгоритмы не является полиномиальными И еще тебе потребуются ВСЕ документы то есть с ростом базы это тоже будет не быстро.  А после обрезки и вообще невозможно ))))

посмотрел повнимательнее, то что я нашел - не то, что надо. эти алгоритмы находят приближенное решение, с условием, что сумма весов НЕ БОЛЬШЕ указанного значения. а мне надо алгоритм, который получает все наборы(ну или в крайнем случае первый попавшийся), сумма весов которых РАВНА указанному значению

up.. неужели никто не делал?

Таких может и не быть. Попробуйте неявную схему перебора, причем имеет смысл начинать с больших сумм. И попробовать сделать отсечение.

проще развернуть по документам, делающим движения...

Симплекс метод)

Если бы не нашел готовый алгоритм я бв сделал так: 1 упорядочить массив 2. для каждого элемента массива подбираю сумму других элементов при этом перебираю только те элементы которые меньше и не больше остатка суммы. по идеи в итоге должен получить все комбинации.