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

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

Введение

Задача рюкзака — это оптимизационная задача, в которой нужно определить, какие предметы положить в рюкзак (ранец) ограниченной вместимости, чтобы максимизировать суммарную стоимость. Предметы могут быть как целыми, так и дробными. В этой главе мы рассматриваем только целочисленный вариант (0/1 knapsack), поскольку дробный вариант решается жадно.

Постановка:
Дано $N$ предметов, каждый имеет вес и стоимость, и рюкзак вместимостью $W$ ($W > 0$). Нужно выбрать некоторые предметы так, чтобы их суммарный вес не превышал $W$, а суммарная стоимость была максимальной. Предметы нельзя делить на части.

Пример: при $W = 5$, и предметах , , (первое число — стоимость, второе — вес) можно получить максимальную стоимость , положив в рюкзак и (вес ).