Задача о рюкзаке и связанные задачи - История изменений

Ctrlalt: /* Каким минимальным количеством предметом можно набрать сумму targetSum */

2025-11-19T00:38:03Z

Каким минимальным количеством предметом можно набрать сумму targetSum

← Предыдущая версия		Версия от 00:38, 19 ноября 2025
Строка 576:		Строка 576:
	\|}		\|}

	=== Каким минимальным количеством ~~предметом~~ можно набрать сумму targetSum ===		=== Каким минимальным количеством предметов можно набрать сумму targetSum ===

	==== O(items.size() * targetSum) памяти ====		==== O(items.size() * targetSum) памяти ====

Ctrlalt: /* Примеры кода */

2025-11-19T00:35:18Z

Примеры кода

← Предыдущая версия		Версия от 00:35, 19 ноября 2025
Строка 376:		Строка 376:
	=== Можно ли набрать сумму targetSum ===		=== Можно ли набрать сумму targetSum ===

	==== ~~Базовый вариант~~ ====		==== O(items.size() * targetSum) памяти ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 415:		Строка 415:
	\|}		\|}

	==== ~~Вернуть~~ сертификат (список предметов) ====		==== O(items.size() * targetSum) памяти, вернуть сертификат (список предметов) ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 488:		Строка 488:
	\|}		\|}

	==== ~~Базовый вариант,~~ O(targetSum) памяти ====		==== O(targetSum) памяти ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 521:		Строка 521:
	\|}		\|}

	==== ~~Вернуть~~ сертификат (список предметов)~~, O(targetSum) памяти~~ ====		==== O(targetSum) памяти, вернуть сертификат (список предметов) ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 578:		Строка 578:
	=== Каким минимальным количеством предметом можно набрать сумму targetSum ===		=== Каким минимальным количеством предметом можно набрать сумму targetSum ===

	==== ~~Базовый вариант~~ ====		==== O(items.size() * targetSum) памяти ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 621:		Строка 621:
	\|}		\|}

	==== ~~Вернуть~~ сертификат (список предметов) ====		==== O(items.size() * targetSum) памяти, вернуть сертификат (список предметов) ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 696:		Строка 696:
	\|}		\|}

	==== ~~Базовый вариант,~~ O(targetSum) памяти ====		==== O(targetSum) памяти ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 729:		Строка 729:
	\|}		\|}

	==== ~~Вернуть~~ сертификат (список предметов)~~, O(targetSum) памяти~~ ====		==== O(targetSum) памяти, вернуть сертификат (список предметов) ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 765:		Строка 765:
	=== Сколько есть способов набрать сумму targetSum (без учёта порядка, 1 + 2 == 2 + 1) ===		=== Сколько есть способов набрать сумму targetSum (без учёта порядка, 1 + 2 == 2 + 1) ===

	==== ~~Базовый вариант~~ ====		==== O(items.size() * targetSum) памяти ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 806:		Строка 806:
	\|}		\|}

	==== ~~Базовый вариант,~~ O(targetSum) памяти ====		==== O(targetSum) памяти ====
	{\|		{\|
	\|width=50%\| Предмет каждого вида ровно один		\|width=50%\| Предмет каждого вида ровно один
Строка 845:		Строка 845:
	\|-		\|-
	\|		\|
			(O(targetSum * items.size()) памяти.)
	long long getOrderedWays(vector<int> &items, int targetSum) {		long long getOrderedWays(vector<int> &items, int targetSum) {
	vector<vector<long long>> ways(targetSum + 1, vector<long long>(items.size() + 1));		vector<vector<long long>> ways(targetSum + 1, vector<long long>(items.size() + 1));
Строка 861:		Строка 862:
	\|		\|
	\|		\|
			(O(targetSum) памяти. По сути, это другая формулировка задачи о кузнечике.)
	long long getOrderedWays(vector<int> &items, int targetSum) {		long long getOrderedWays(vector<int> &items, int targetSum) {
	vector<long long> ways(targetSum + 1);		vector<long long> ways(targetSum + 1);
Строка 872:		Строка 874:
	return ways[targetSum];		return ways[targetSum];
	}		}

	~~(O(targetSum) памяти. По сути, это другая формулировка задачи о кузнечике.)~~
	\|}		\|}

Ctrlalt: /* Примеры кода */

2025-11-19T00:03:05Z

Примеры кода

Внесённые изменения

Ctrlalt: /* Also */

2025-11-18T23:26:34Z

Also

Внесённые изменения

Ctrlalt: /* Also */

2021-11-26T17:27:36Z

Also

← Предыдущая версия		Версия от 17:27, 26 ноября 2021
Строка 421:		Строка 421:
	minCoins[sum] = min(minCoins[sum], minCoins[sum - coin] + 1);		minCoins[sum] = min(minCoins[sum], minCoins[sum - coin] + 1);

	return minCoins[~~sum~~] != 1e9 ? minCoins[~~sum~~] : -1;		return minCoins[targetSum] != 1e9 ? minCoins[targetSum] : -1;
	}		}
	\|		\|
Строка 433:		Строка 433:
	minCoins[sum] = min(minCoins[sum], minCoins[sum - coin] + 1);		minCoins[sum] = min(minCoins[sum], minCoins[sum - coin] + 1);

	return minCoins[~~sum~~] != 1e9 ? minCoins[~~sum~~] : -1;		return minCoins[targetSum] != 1e9 ? minCoins[targetSum] : -1;
	}		}
	\|}		\|}

Ctrlalt: /* Also */

2021-05-22T22:27:31Z

Also

@@ Строка 376: / Строка 376: @@
 Можно ли монетами coins набрать сумму targetSum?
 {|
-| Есть лишь одна монета каждого вида
+|width=50%| Есть лишь одна монета каждого вида
 | &nbsp;
-| Монет каждого вида неограниченно много
+|width=50%| Монет каждого вида неограниченно много
 |-
+|
@@ Строка 404: / Строка 404: @@
+  }
 |}
 == Ссылки ==
 * [http://algorithmica.org/tg/knapsack-gis-gcs algorithmica.org — Задача о рюкзаке, НВП и НОП]

Ctrlalt в 22:13, 22 мая 2021

2021-05-22T22:13:04Z

@@ Строка 372: / Строка 372: @@
 Временная сложность решения Θ(NM). Для таблицы требуется Θ(NM) или Θ(M) памяти.
 == Ссылки ==
 * [http://algorithmica.org/tg/knapsack-gis-gcs algorithmica.org — Задача о рюкзаке, НВП и НОП]

Ctrlalt в 19:47, 27 декабря 2020

2020-12-27T19:47:52Z

← Предыдущая версия		Версия от 19:47, 27 декабря 2020
Строка 371:		Строка 371:

	Временная сложность решения Θ(NM). Для таблицы требуется Θ(NM) или Θ(M) памяти.		Временная сложность решения Θ(NM). Для таблицы требуется Θ(NM) или Θ(M) памяти.

			== Ссылки ==
			* [http://algorithmica.org/tg/knapsack-gis-gcs algorithmica.org — Задача о рюкзаке, НВП и НОП]
			* [https://brilliant.org/wiki/backpack-problem/ brilliant.org — Backpack Problem]

	[[Категория:Динамическое программирование]]		[[Категория:Динамическое программирование]]

Ctrlalt в 19:12, 27 декабря 2020

2020-12-27T19:12:04Z

← Предыдущая версия		Версия от 19:12, 27 декабря 2020
Строка 371:		Строка 371:

	Временная сложность решения Θ(NM). Для таблицы требуется Θ(NM) или Θ(M) памяти.		Временная сложность решения Θ(NM). Для таблицы требуется Θ(NM) или Θ(M) памяти.

			[[Категория:Динамическое программирование]]

Ctrlalt в 19:10, 27 декабря 2020

2020-12-27T19:10:13Z

← Предыдущая версия		Версия от 19:10, 27 декабря 2020
Строка 63:		Строка 63:

	bool solve(const vector<int> &itemWeight, int targetWeight) {		bool solve(const vector<int> &itemWeight, int targetWeight) {
	vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1)); ~~// создаём таблицу, заполненную false~~		vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));

	canMake[0][0] = true; ~~// нулём предметов мы можем набрать только вес 0~~		canMake[0][0] = true;

	for (int items = 1; items <= itemWeight.size(); items++) {		for (int items = 1; items <= itemWeight.size(); items++) {
	int currentItemWeight = itemWeight[items - 1]; ~~// вес текущего предмета~~		int currentItemWeight = itemWeight[items - 1];

	for (int weight = 0; weight <= targetWeight; weight++) {		for (int weight = 0; weight <= targetWeight; weight++) {
	if (canMake[items - 1][weight]) ~~// если предыдущими предметами могли набрать вес weight, то и сейчас можем набрать вес weight~~		if (canMake[items - 1][weight])
	canMake[items][weight] = true;		canMake[items][weight] = true;

	if (weight >= currentItemWeight && canMake[items - 1][weight - currentItemWeight])		if (weight >= currentItemWeight && canMake[items - 1][weight - currentItemWeight])
	canMake[items][weight] = true; ~~// если предыдущими предметами могли набрать вес (weight - currentItemWeight), то сейчас можем набрать вес weight~~		canMake[items][weight] = true;
	}		}
	}		}
Строка 114:		Строка 114:
	canMake[items][weight] = true;		canMake[items][weight] = true;

	if (weight >= currentItemWeight && canMake[items][weight - currentItemWeight])		if (weight >= currentItemWeight && canMake[{{Changed\|items}}][weight - currentItemWeight])
	canMake[items][weight] = true;		canMake[items][weight] = true;
	}		}
Строка 161:		Строка 161:
	int currentItemWeight = itemWeight[items - 1];		int currentItemWeight = itemWeight[items - 1];

	for (int weight = targetWeight; weight >= currentItemWeight; weight--) {		for ({{Changed\|1=int weight = targetWeight; weight >= currentItemWeight; weight--}}) {
	if (canMake[weight - currentItemWeight])		if (canMake[weight - currentItemWeight])
	canMake[weight] = true;		canMake[weight] = true;
Строка 232:		Строка 232:
	И так далее, от конца к началу мы определяем, брали или нет мы каждый из предметов, попутно уменьшая weight.		И так далее, от конца к началу мы определяем, брали или нет мы каждый из предметов, попутно уменьшая weight.

	vector<int> solve(const vector<int> &itemWeight, int targetWeight) {		{{Changed\|vector<int>}} solve(const vector<int> &itemWeight, int targetWeight) {
	vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));		vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));
	vector<vector<bool>> take(itemWeight.size() + 1, vector<int>(targetWeight + 1));		{{Changed\|vector<vector<bool>> take(itemWeight.size() + 1, vector<int>(targetWeight + 1));}}

	canMake[0][0] = true;		canMake[0][0] = true;
Строка 247:		Строка 247:
	if (weight >= currentItemWeight && canMake[items - 1][weight - currentItemWeight]) {		if (weight >= currentItemWeight && canMake[items - 1][weight - currentItemWeight]) {
	canMake[items][weight] = true;		canMake[items][weight] = true;
	take[items][weight] = true;		{{Changed\|1=take[items][weight] = true;}}
	}		}
	}		}
	}		}

	if (!canMake[itemWeight.size()][targetItem])		{{Changed\|1=if (!canMake[itemWeight.size()][targetItem])}}
	return {};		{{Changed\|1=return {};}}

	vector<int> takenItemIndexes;		{{Changed\|1=vector<int> takenItemIndexes;}}
	for (int items = itemWeight.size(), weight = targetWeight; items > 0; items--) {		{{Changed\|1=for (int items = itemWeight.size(), weight = targetWeight; items > 0; items--) {}}
	if (take[items][weight]) {		{{Changed\|1=if (take[items][weight]) {}}
	takenItemIndexes.push_back(items - 1);		{{Changed\|1=takenItemIndexes.push_back(items - 1);}}
	weight -= itemWeight[items - 1];		{{Changed\|1=weight -= itemWeight[items - 1];}}
	}		{{Changed\|1=} }}
	}		{{Changed\|1=} }}
	return takenItemIndexes;		{{Changed\|1=return takenItemIndexes;}}
	}		}

Строка 317:		Строка 317:
	Решаем задачу о сумме подмножеств, ищем самое правое true в последней строке таблицы.		Решаем задачу о сумме подмножеств, ищем самое правое true в последней строке таблицы.

	int solve(const vector<int> &itemWeight, int targetWeight) {		{{Changed\|int}} solve(const vector<int> &itemWeight, int targetWeight) {
	vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));		vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));

Строка 334:		Строка 334:
	}		}

	while (!canMake[items.size()][targetWeight])		{{Changed\|1=while (!canMake[items.size()][targetWeight])}}
	targetWeight--;		{{Changed\|1=targetWeight--;}}
	return targetWeight;		{{Changed\|1=return targetWeight;}}
	}		}

Строка 345:		Строка 345:
	Решаем задачу о сумме подмножеств для targetWeight == (сумма весов предметов) / 2.		Решаем задачу о сумме подмножеств для targetWeight == (сумма весов предметов) / 2.

	~~int~~ solve(const vector<int> &itemWeight) {		bool solve(const vector<int> &itemWeight) {
	vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));		vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));

	int targetWeight = 0;		{{Changed\|1=int targetWeight = 0;}}
	for (int weight : itemWeight)		{{Changed\|1=for (int weight : itemWeight)}}
	targetWeight += weight;		{{Changed\|1=targetWeight += weight;}}
	targetWeight /= 2;		{{Changed\|1=targetWeight /= 2;}}

	canMake[0][0] = true;		canMake[0][0] = true;