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

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

Первое, что тна ум приходит что-то в этом роде: (S - искомая сумма, i - элементы сумм).

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

Потом этот же цикл, но начать с i2.

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

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

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

(1) спасибо
http://lib.custis.ru/Задача_о_рюкзаке:PTAS
http://lib.custis.ru/Задача_о_рюкзаке:жадный_алгоритм

(6) тока алгоритм
Жадный алгоритм имеет сложность O(n log(n)), и гарантирует нахождение решения, не хуже чем в два раза от оптимального.

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

И еще тебе потребуются ВСЕ документы то есть с ростом базы это тоже будет не быстро.  А после обрезки и вообще невозможно ))))

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

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

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

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

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

Нужен алгоритм набора нужной суммы

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