Задача о рюкзаке — это задача комбинаторной оптимизации: для заданного набора предметов, каждый из которых имеет вес и ценность, определить количество каждого предмета, которое нужно включить в коллекцию, чтобы общий вес был меньше или равен заданному пределу и общая стоимость как можно больше. Его название связано с проблемой, с которой сталкивается тот, кто ограничен рюкзаком фиксированного размера и должен наполнить его самыми ценными предметами. В этой статье мы разберем некоторые..