Российский экономический

 
7.6. Задачи о контейнере (рюкзаке, ранце) 
Задачи оптимальной загрузки емкости — рюкзака туриста, ранца школь-
ника, контейнера на железнодорожном транспорте, самолета, трюма корабля, 
вагона поезда, склада в логистике для нахождения оптимальной загрузки, раз-
мещение грузов в помещении малого объема, раскройка ткани для заданного 
179

---

куска материала — получить максимальное число выкроек определенной фор-
мы, расчет оптимальных капиталовложений. В общем виде задачу можно 
сформулировать так: из заданного множества предметов с известными данными 
«стоимость» и «вес» требуется отобрать число предметов таким образом, чтобы 
получить максимальную суммарную стоимость при одновременном соблюде-
нии ограничений. Существуют шесть различных разновидностей этой задачи: 

рюкзак 0-1. Классическая задача о ранце: не более одного экземпляра 
каждого вида предмета, причем
каждую вещь можно либо положить в рюкзак, 
либо нет. Все вещи в единственном экземпляре; 

ограниченный рюкзак: не более заданного числа экземпляров каждого 
предмета, каждую вещь можно взять ограниченное число раз, для загрузки до-
ступно несколько конечных множеств однотипных вещей; 

неограниченный рюкзак, целочисленный рюкзак: произвольное коли-
чество экземпляров каждого предмета.
Каждую вещь можно взять неограни-
ченное число раз, количество вещей каждого типа значительно больше, чем 
может поместиться в рюкзак; 

рюкзак с мультивыбором.
Все предметы делятся на определенные 
классы. Обязательным является условие выбора предмета из каждого класса; 

мультипликативный рюкзак: есть несколько рюкзаков, каждый со сво-
им максимальным весом. Каждый предмет можно положить в любой рюкзак 
или оставить.
Имеется несколько рюкзаков с разной вместимостью, необходи-
мо максимизировать суммарную стоимость рюкзаков; 

многомерный рюкзак: дано несколько разных ресурсов, например, вес, 
объем и время укладки. Каждый предмет потребляет определенное количество 
каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие за-
траты каждого ресурса не превышали максимума по этому ресурсу, при этом 
общая ценность предметов была бы максимальна.
Существуют разные методы решения таких задач: метод простого полно-
го перебора, метод ветвей и границ, динамическое программирование, неточ-
ные методы, но более быстрые: жадный алгоритм, генетический алгоритм.
1. Грабитель, проникший в банк, обнаружил в сейфе 100 золотых слитков 
группы по 20 шт. весом по 2, 3, 4, 5, 6 кг. При этом грабитель может унести в 
рюкзаке не более 43 кг. Определите набор слитков, который должен взять гра-
битель, чтобы быстро унести как можно больше золота.
2. Максимальная вместимость рюкзака — 15 кг, количество предметов — 
5, их стоимости (тыс. руб.) и массы (кг) соответственно равны: 6 и 5; 4 и 3; 3 
и 1; 2 и 3; 5 и 6.
Определите набор 
предметов
, который обеспечит
наилучший 
вариант компановки.
3. Имеется рюкзак вместимостью 13 кг и пять вещей. 
Таблица