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

Задача о ранце (или «о рюкзаке«) [problem of knapsack] — задача о наилучшем выборе предметов из общего их количества таким образом, чтобы их суммарный вес (или габариты и т.п.) не превышал заданного, а их суммарная полезность, или иная общая оценка, была максимальной. Решается как задача целочисленного линейного программирования, методами динамического программирования и др. Применяется, например, при планировании оптимальной загрузки самолетов, кораблей, складов.

  • · Упрощенно модель задачи о ранце можно записать так:

Найти

т.е. наибольшую ценность груза (xi — количество, vi — стоимость предмета i-го вида, i = 1, 2, …, n);

при условиях:

т.е. вес груза не превышает грузоподъемности ранца W (pi — вес i-го предмета);

xi = 0, 1, 2,..

Последнее условие говорит о том, что предметы неделимы (условие целочисленности).