Задача о ранце.

Пусть имеется n предметов, которые могут быть полезны в походе. Полезность i-го предмета оценивается
числом ai, вес предмета (или его объем) - bi. Суммарный вес, который может нести турист (объем рюкзака), ограничен величиной R.
Требуется найти набор предметов, обладающий максимальной суммарной полезностью и удовлетворяющий ограничению.
Обозначим xi - переменную, принимающую значение ноль (если i-ый предмет не кладется в ранец) или единица (если i-ый предмет кладется в ранец). Тогда задача о ранце имеет вид:
n
Zaixi ® max
i=1 x
Z bx ?R.
i =1
Верхняя оценка числа возможных комбинаций - 2n. Однако для решения задачи о ранце существует эффективный алгоритм - метод динамического программирования. При его использовании строится сеть (см. примеры в [7, 8, 12]) по следующим правилам. По оси абсцисс будем последовательно откладывать номера предметов, по оси ординат - их вес. Из каждой точки (начиная с точки (0; 0)) выходят две дуги - горизонтальная (соответствующая альтернативе «не брать предмет») и наклонная (соответствующая альтернативе «взять предмет»), вертикальная проекция которой равна весу предмета. Длины наклонных дуг положим равными ценности предметов, длины горизонтальных дуг - нулю. Полученная сеть (конечная вершина является фиктивной и вес любой дуги, соединяющей ее с другими вершинами, равен нулю) обладает следующими свойствами: любому решению задачи (6)-(7) соответствует некоторый путь в этой сети; любому пути соответствует некоторое решение задачи. Таким образом, задача свелась к нахождению пути максимальной длины.
<< | >>
Источник: В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. 2001

Еще по теме Задача о ранце.:

  1. 42. проблемная ситуация и задача этапы решения задач способы решения задач.
  2. 15.Постановка задач математической физики. Начальные и граничные условия. Понятие о корректности задачи.
  3. 11.1. Постановка задачи расчета затрат на противопожарную защиту как задачи многокритериальной оптимизации
  4. 2 ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  5. 2П ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  6. § 1.25. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
  7. §1.14. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
  8. § 9.5. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
  9. § 7.2. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
  10. §7.10. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
  11. Блок 2. Технология решения психологических задач Занятие 3 Технологии решения психологических задач.
  12. Задача распределения объемов работ.
  13. 2.1. ЗАДАЧИ О НАЗНАЧЕНИИ
  14. 5.5.2. NP задачи
  15. 5.5.1. Р задачи
  16. Решение двойственных задач
  17. Транспортная задача.