2.3.1.2. Метод укладки (упаковки) рюкзака (ранца)

Реализацией задачи об укладке рюкзака является криптоалгоритм Мер-кле и Хелмана. Рассмотрим этот криптоалгоритм на примере. Пусть задан набор чисел

(а,,а₂,...а_п) = А.

Задачей является нахождение таких чисел а_|5 если это возможно, сумма которых равна числу к. В простейшем случае это число к указывает размер рюкзака, а каждое из чисел а. указывает размер предмета, который может быть упакован в рюкзак. Задачей является нахождение тако­го набора предметов, чтобы рюкзак был полностью заполнен.

В качестве примера возьмем число к=3231 и набор из 10 целых чисел а^...,

^аю^:

43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523.

Заметим, что число k получается при сложении только некоторых чи­сел а:

Рис. 5.28. Метод укладки рюкзака

3231 = 129+ 473 + 903 + 561 + 1165

Таким образом, сложив эти числа, мы нашли решение, то есть заполни­ли рюкзак. Ситуация наглядно проиллюстрирована на рис. 5.28.

В принципе решение всегда может быть найдено полным перебором подмножеств А и проверкой, какая из сумм равна числу к. В нашем случае это означает перебор 2¹⁰=1024 подмножеств (включая при этом и пустое множество). Это вполне осуществимо.

Но что будет, если существует несколько сотен чисел а/? В нашем примере п=10, чтобы не усложнять положение и расчеты. В реальных условиях при­мер будет иметь, скажем, 300 чисел а.. Суть здесь в том, что неизвестны алго­ритмы, имеющие существенно меньшую сложность по сравнению с полным перебором. Поиск правильного решения среди 2³⁰⁰ подмножеств не поддается обработке.