Задача о ранце (или «о рюкзаке«) [problem of knapsack] — задача о наилучшем выборе предметов из общего их количества таким образом, чтобы их суммарный вес (или габариты и т.п.) не превышал заданного, а их суммарная полезность, или иная общая оценка, была максимальной. Решается как задача целочисленного линейного программирования, методами динамического программирования и др. Применяется, например, при планировании оптимальной загрузки самолетов, кораблей, складов.
- · Упрощенно модель задачи о ранце можно записать так:
Найти
т.е. наибольшую ценность груза (xi — количество, vi — стоимость предмета i-го вида, i = 1, 2, …, n);
при условиях:
т.е. вес груза не превышает грузоподъемности ранца W (pi — вес i-го предмета);
xi = 0, 1, 2,..
Последнее условие говорит о том, что предметы неделимы (условие целочисленности).