При работе на складе я столкнулся с алгоритмом подбора суммы из чисел. Например,
нужно было выдать со склада нужное количесто товара, но в разных ячейках склада
лежало разное количество и нужно было так выбрать ячейки, чтобы по возможности
забирать из ячеек весь товар.
До применения этого алгоритма одна из ячеек (последняя) разбивалась так, чтобы
подобрать нужное количество. Теперь же, оснащенная этим алгоритмом программа,
может высвобождать на одну ячейку больше по каждому товару.
В принципе, алгоритм подходит и для других задач, где нужно набрать нужную сумму из нескольких чисел.
Постановка задачи.
Имеется список List из n положительных чисел {N[1], N[2], ... N[n]}. Нужно
найти список позиций{P[1], P[2], ... P[m]}, m<=n, чтобы сумма по i=1..m чисел
N[P[i]] была равна заданной S.
Например, для списка {11, 16, 8, 4, 7 , 6, 3, 12 } и суммы 19 решениями могут
быть {1, 3 } = 11+8 или {2, 7} = 16+3 или {5, 8} = 7+12
Алгоритм.
Попробуем решить задачу для частных случаев, в начале Pos=1.
1. Если S меньше либо равна нуля или размер списка равен нулю, то задача не
решается.
2. Если первый элемент First списка List равен S, решением будет список, состоящий
из одного элемента текущей позиции анализа Pos.
3. Если в списке один элемент и не выполняется 2, то задача не решается.
Если задача не подпадает под частные случаи, выделяем из списка подсписок SubList,
получающийся из исходного отбрасыванием первого элемента.
Теперь для того, чтобы решить задачу, нужно найти решение одной из двух задач
для списка SubList, позиции Pos+1 и суммы Summ-First или Summ.
Как только получили решение одной из подзадач список SubResultList, результат
задачи получается вставкой Pos в начало списка SubResultList.
Если и в подсписках нет решения, задача не решается.
Реализация на алгоритмическом языке.
Алгорим реализован на языке программирования 1С. Но его легко переписать на любой бейсик-подобный язык, допускающий рекурсивные вызовы процедур. Для интересующихся скачать обработку на 1С, демонстрирующую алгорим, можно в разделе ""Разработки".