Задача об укладке рюкзака. Задано множество {vi} из k натуральных чисел и целое число S.
Требуется найти такое k-разрядное число n = (nk – 1nk – 2…n1n0)2 (где ni Î {0, 1} суть значения разрядов в двоичной записи чиcла n), что , если такое n существует.
В зависимости от набора {vi} и числа S, такого решения может не быть вообще, решений может быть несколько или решение будет единственным. Такая задача является сложной.
Частный случай – задача об укладке быстровозрастающего рюкзака. Это случай, когда величины vi, будучи упорядочены в порядке возрастания, обладают тем свойством, что каждое число больше суммы всех предыдущих.
Такая задача имеет эффективный алгоритм решения:
1. Положим W = S и j = k.
2. Начиная с nj – 1 и последовательно уменьшая j, полагаем все nj = 0 до тех пор, пока не придем к первому такому значению j (обозначим его через i0), что . Положим
3. Заменим W на , положим j = i0 и, если W > 0, то переходим к шагу 2.
4. Если W = 0, то цель достигнута. Если W > 0 и все оставшиеся vi больше W, то ясно, что решения n = (nk – 1nk – 2…n1n0)2 задачи не существует. Если решение есть, то оно единственное.
Пример. Набор {2, 3, 7, 15, 31} является быстрорастущим набором, а S = 24. Тогда проходя пятерку значений справа налево, мы видим, что n4 = 0 (31 > 24), n3 = 1 (15 < 24 и в этот момент заменяем 24 на 24 – 15 = 9), n2 = 1 (7 < 9 и в этот момент заменяем 9 на 9 – 7 = 2), n1 = 0 (3 > 2), n0 = 1 (2 = 2). Таким образом, получаем n = (01101)2 = 13.