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

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