ЗАДАЧА О РАНЦЕ (KNAPSACK PROBLEM)

задача программирования целочисленного: имеется ранец объема V и неограниченное кол-во каждого из Л различных предметов. Для каждого предмета 1-го типа при (-1,2,..., N известны его объем Vi и ценность т/. В ранец можно положить целое число предметов разного типа. При этом цель состоит в том, чтобы суммарная стоимость всех находящихся в ранце предметов была максимальна, а их объем не превышал величины У. 3. о р. может также решаться Гомори методом, методами программирования дин. и др. К 3. о р. может быть сведена задача макс, использования грузоподъемности подвижного состава, грузовместимости судна и т.п.