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

Задача о ранце (рюкзаке) — одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами „стоимость“ и „вес“, требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес. Существует 2 разновидности задачи о ранце:

1. Каждый предмет из множества можно выбирать бесконечное кол-во раз.
2. Каждый предмет можно использовать только один раз.

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

Задача о ранце с возможностью бесконечного выбора предметов

Формулировка

По данному набору из n предметов стоимостями $v_{1},v_{2},...,v_{n}$ и весами $w_{1},w_{2},...,w_{n}$ найти поднабор(с учетом того, что можно брать один предмет несколько раз), такой что его стоимость будет максимальна, среди всех поднаборов веса не более W.

Решение

Обозначим через $K_{w}$ максимальную стоимость, которую мы можем набрать при весе не более w. Получаем следующее рекуррентное соотношение:

• $K_{0}$ = 0 (при весе не более нуля максимальная стоимость 0)
• $K_{w}$ = max { $K_{w-w_{i}}+v_{i}|w_{i}<=w$, 1 <= i <= n, где n - размер набора }

Использовать рекурсию напрямую нельзя, т.к. появляется большое число перекрывающихся задач и время выполнения может стать экспоненциальным. При использовании динамического программирования(запоминания) мы получаем сложность O(n * W) - псевдо-полиномиальный алгоритм.

Реализация

C++

#include <vector>
#include <limits>

//wts - массив весов, cost - массив стоимостей предметов, W - вместимость рюкзака
//функция возвращает максимальную стоимость, которую можно набрать(решение задачи о рюкзаке
//с повторениями)
//массив dp собственно реализует динамическое программирование, описанное в статье, как K_w
int knapsack1(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
	size_t n = wts.size();
	std::vector<int> dp(W + 1);
	dp[0] = 0;
	for (int w = 1; w <= W; w++)
	{
		dp[w] = std::numeric_limits<int>::min();
		for (size_t i = 0; i < n; i++)
		{
			if (wts[i] <= w)
			{
				dp[w] = std::max(dp[w], dp[w - wts[i]] + cost[i]);
			}
		}
	}
	return dp[W];
}

Задача о ранце с возможностью единичного выбора предмета

Формулировка

Как и в задаче выше, только каждый предмет можно выбирать один раз.

Решение

Обозначим через $K_{w,i}$ максимальную стоимость, которую мы можем набрать при весе не более w среди i первых предметов. Получаем следующее рекуррентное соотношение:

• $K_{0,j}$ = 0, 0 <= j <= n
• $K_{w,0}$ = 0, 0 <= w <= W
• $K_{w,i}$ = max{$K_{w,i-1}$, $K_{w-w_{i},i-1}$} | 0 <= w <= W, $w_{i}$ <= w}
• $K_{w,i}$ = $K_{w,i-1}$, если $w_{i}$ > w (не можем положить предмет данного веса)

Не верно т.к. по этому рекуррентному соотношению значение функции 0.

Реализация

C++

#include <vector>
#include <limits>

int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
	size_t n = wts.size();
	std::vector<std::vector<int> > dp(W + 1);
	for (int i = 0; i <= W; i++)
	{
		dp[i].resize(n + 1);
		dp[i][0] = 0;
	}
	for (size_t i = 0; i <= n; i++)
	{
		dp[0][i] = 0;
	}
	for (size_t j = 1; j <= n; j++)
	{
		for (int w = 1; w <= W; w++)
		{
			if (wts[j] <= w)
			{
				dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j]][j - 1] + cost[j]);
			} else
			{
				dp[w][j] = dp[w][j - 1];
			}
		}
	}
	return dp[W][n];
}

См. также

• Задача об упаковке в контейнеры

хуй

Литература

• Ананий В. Левитин. Глава 3. Метод грубой силы: Задача о рюкзаке // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 160-163. — ISBN 0-201-74395-7.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2.