Задача о ранце.
числом 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) соответствует некоторый путь в этой сети; любому пути соответствует некоторое решение задачи. Таким образом, задача свелась к нахождению пути максимальной длины.