Задача о ранце
Пусть имеется некоторый объем V, который необходимо заполнить различными предметами. Предметов имеется несколько видов, отличающихся объемом v(i) и ценностью c(i).
Требуется определить вариант заполнения предметами объема V, чтобы их суммарная ценность оказалась наибольшей. Неизвестные переменные задачи — это x(i) — число предметов i-го вида, выбранных для размещения в ранце. Ограничения задачи имеют вид:
x(1) v(1) + x(2) v(2) + ... + x(n) v(n) < V;
x(i) > 0.
Оценка вариантов решения задачи — это сумма
J = x(1) c(1) + x(2) c(2) + ... + x(n)c(n), которая должна иметь максимальное значение.
Похожие рефераты:
