Задача о рюкзаке

Постановка задачи. Имеется неделимых предметов и для каждого предмета известно его вес и стоимость. Требуется некоторую часть этих предметов уложить в рюкзак, причём так, чтобы их суммарная стоимость была не меньше , и вес рюкзака был минимальным.

Математическая модель. Введём неизвестные

тогда ограничения по стоимости будут: (6) Целевая функция:

Для решения этой задачи эффективен метод ветвей и границ. При этом первое предположение реализуется следующим образом:

Пусть есть некоторое подмножество . Оно характеризуется ещё не уложенными в рюкзак предметами. Пусть мы ещё не приняли решение по предмету . Тогда можно разбить на два подмножества:

Второе предположения реализуется следующим образом:

Пусть дано некоторое подмножество , которое характеризуется неуложенными предметами. Для каждого неуложенного предмета считается отношение , то есть относительный вес на единицу стоимости. Далее считаем, что неуложенные предметы можно дробить в любой части и в любой доли засыпать в рюкзак. Затем решается непрерывная задача о рюкзаке. Ясно, что в первую очередь из неуложенных предметов нужно брать те, которые имеют наименьшее отношение . В порядке возрастания этих чисел засыпаем оставшиеся предметы в рюкзак, пока в точности не выполнится равенство . Остальные предметы (которые не вошли) остаются не уложенными (может так оказаться, что один из предметов целиком в рюкзак не вошёл). Вес рюкзака и принимается за оценку снизу. Далее реализуется общая схема метода ветвей и границ.