Перебор вариантов с помощью дерева

• Грузоподъёмность рюкзака (${\displaystyle W}$) — максимальный допустимый вес всех выбранных предметов.
• Предметы — набор из ${\displaystyle n}$ вещей, каждая из которых имеет вес ${\displaystyle w_{i}}$ и ценность ${\displaystyle v_{i}}$, где ${\displaystyle i=1,2,\ldots ,n}$.
• Переменные выбора — бинарные переменные ${\displaystyle x_{i}\in \{0,1\}}$, определяющие, выбран предмет (${\displaystyle x_{i}=1}$) или нет (${\displaystyle x_{i}=0}$).

Необходимо:

• максимизировать функцию ценности:

 ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i},}$

• при ограничении на суммарный вес:

 ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W.}$

Перебор всех возможных комбинаций предметов (всего имеется ${\displaystyle n}$ предметов) для нахождения оптимального решения.

Для каждого предмета существует 2 варианта: предмет кладётся в рюкзак, либо предмет не кладётся в рюкзак. Количество вариантов растёт экспоненциально с увеличением числа предметов (${\displaystyle 2^{n}}$), поэтому метод применим только для малых значений ${\displaystyle n}$.

На рисунке показано дерево перебора для трёх предметов. Каждый лист соответствует некоторому подмножеству предметов. После составления дерева необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает ${\displaystyle W}$.

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

Эффективно решает задачу при целочисленных весах предметов. Временная сложность метода — ${\displaystyle O(nW)}$, где ${\displaystyle n}$ — количество предметов, ${\displaystyle W}$ — грузоподъёмность рюкзака.

Рекуррентное соотношение:

• Инициализация:

 ${\displaystyle m[0,w]=0,\quad \forall w\leq W.}$

• Рекуррентные формулы:

 ${\displaystyle m[i,w]={\begin{cases}m[i-1,w],&w_{i}>w,\\\max \left(m[i-1,w],\;m[i-1,w-w_{i}]+v_{i}\right),&w_{i}\leq w.\end{cases}}}$

Здесь ${\displaystyle m[i,w]}$ — максимальная ценность при рассмотрении первых ${\displaystyle i}$ предметов и суммарном весе не более ${\displaystyle w}$.

Заключается в сортировке предметов по убыванию удельной ценности (${\displaystyle v_{i}/w_{i}}$) и последовательном добавлении их в рюкзак до достижения ограничения по весу. Даёт оптимальное решение для непрерывной версии задачи, но не гарантирует оптимальности в дискретном случае.

• Планирование загрузки: оптимизация размещения грузов при ограниченной грузоподъёмности транспорта.
• Инвестиционный портфель: выбор проектов для инвестирования при ограниченном бюджете.
• Раскрой материалов: минимизация отходов при раскрое ресурсов (ткань, металл и др.).
• Криптография: основа для построения некоторых алгоритмов шифрования, например, ранцевой криптосистемы Меркла — Хеллмана.

Задача о рюкзаке является важной в теории алгоритмов и имеет множество практических приложений. Несмотря на её вычислительную сложность, существуют эффективные методы, позволяющие находить точные и приближённые решения, что делает её полезной в различных областях науки и техники.