На этом шаге мы сформулируем эту задачу.

    Алгоритмы перебора с возвратами применяются также для решения задач оптимизации. В задаче о рюкзаке 0-1 у нас есть множество из n предметов со стоимостями v_i и весами w_i, где i = 0, ..., n - 1. Цель задачи - найти такое подмножество предметов, чтобы их суммарный вес не превышал грузоподъёмности C рюкзака, а суммарная стоимость была максимальной. Формально задачу оптимизации можно записать так: максимизировать

          n-1
          ∑ xivi
          i=0

          n-1
          ∑ xivi ≤ C   ,
          i=0

    Вектор или список x = [x₁, ..., x_n] - переменная величина задачи (её частичное решение), компоненты которой могут принимать значения 0 или 1. В частности, x_i = 1 означает, что предмет под номером i помещён в рюкзак. Таким образом, x играет ту же роль, что и двоичный список в задаче генерации подмножеств или в задаче о сумме подмножества.

    Сумма

          n-1
          ∑ xivi
          i=0

          n-1
          ∑ xivi ≤ C   
          i=0

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

    На следующем шаге мы рассмотрим стандартный алгоритм перебора с возвратами.

Предыдущий шаг Содержание Следующий шаг