Задача о рюкзаке: Классика дискретной оптимизации

Математически эта задача имеет несколько вариантов, требующих совершенно разных алгоритмических подходов к решению:

1. Непрерывная (дробная) задача о рюкзаке. Допустим, мы крадем не неделимые предметы, а сыпучие материалы: золотой песок, серебряную стружку, муку. В этом случае мы можем отсыпать любую долю (дробную часть) от предмета. Эта версия решается элементарным Жадным алгоритмом: мы просто вычисляем "удельную ценность" (стоимость делить на вес) для каждого материала, сортируем их по убыванию этой ценности и начинаем засыпать в рюкзак самые выгодные порошки, пока он не заполнится до краев. Сложность алгоритма всего лишь O(N log N) на сортировку.

2. Классическая 0/1 задача о рюкзаке (0-1 Knapsack). Здесь вещи неделимы: телевизор можно либо взять целиком (1), либо не взять вообще (0). В этом случае жадный алгоритм перестает работать. Если мы жадно возьмем самый выгодный по удельной стоимости, но очень тяжелый предмет, он может заблокировать место для двух чуть менее выгодных, но компактных предметов, которые в сумме дали бы больше прибыли.

Вариант 0/1 является строгой NP-полной задачей. Это означает, что не существует известного полиномиального алгоритма для поиска идеального решения. Однако на практике (если вместимость рюкзака W — целое число и не астрономически велико), задача блестяще решается методом Динамического программирования (ДП).

Алгоритм ДП строит матрицу, где строки — это доступные предметы, а столбцы — все возможные вместимости рюкзака (от 0 до W). Заполняя ячейки по рекурсивной формуле Беллмана (выбирая максимум между ситуациями "взяли предмет" и "не взяли предмет, полагаясь на предыдущие"), мы находим глобальный математический оптимум за псевдополиномиальное время O(N * W). Именно этот алгоритм чаще всего спрашивают на технических собеседованиях в крупные IT-корпорации.

В реальной жизни задача о рюкзаке применяется не для грабежей, а для сугубо инженерных и экономических расчетов: распределение файлов по кластерам серверов (где файл — предмет, а жесткий диск — рюкзак), выбор инвестиционных проектов при ограниченном бюджете кампании, алгоритмы раскроя металла на заводах и генерация ключей в ранних системах асимметричной криптографии (криптосистема Меркла-Хеллмана).