Задача о ранце.
числом 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) соответствует некоторый путь в этой сети; любому пути соответствует некоторое решение задачи. Таким образом, задача свелась к нахождению пути максимальной длины.
Еще по теме Задача о ранце.:
- 42. проблемная ситуация и задача этапы решения задач способы решения задач.
- 11.1. Постановка задачи расчета затрат на противопожарную защиту как задачи многокритериальной оптимизации
- 15.Постановка задач математической физики. Начальные и граничные условия. Понятие о корректности задачи.
- § 1.25. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
- §1.14. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
- § 9.5. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
- § 7.2. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
- §7.10. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ Задача 1
- Блок 2. Технология решения психологических задач Занятие 3 Технологии решения психологических задач.
- 5.5.1. Р задачи
- 5.5.2. NP задачи
- Транспортная задача.
- Решение двойственных задач
- Задачи и функции государства
- Задача с подвижными концами.
- Задача о кратчайшем маршруте
- «Пороговые» учебные задачи