Временная сложность
O(n × W)
Задача о рюкзаке 0/1: даны предметы с определёнными весами и ценностями, а также максимальная вместимость рюкзака. Необходимо найти максимальную суммарную ценность предметов, не превышая вместимость. Каждый предмет можно взять не более одного раза.
Как работает (динамическое программирование снизу вверх):
1. Создаётся двумерная таблица: dp[i][w] = максимальная ценность при использовании первых i предметов и вместимости w
2. Для каждого предмета i и вместимости w:
- Если предмет не помещается: dp[i][w] = dp[i-1][w]
- Если предмет помещается: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
3. dp[n][W] содержит оптимальное значение
Временная сложность: O(n × W) — псевдополиномиальная
Пространственная сложность: O(n × W) — можно оптимизировать до O(W)
Применение:
- Распределение ресурсов
- Планирование бюджета
- Загрузка грузов
- Криптография
Задача о рюкзаке — одна из фундаментальных задач комбинаторной оптимизации и в общем случае является NP-трудной.
Похожие алгоритмы
Частые вопросы
- Что такое Задача о рюкзаке 0/1 (0/1 Knapsack Problem)?
- Задача о рюкзаке 0/1: даны предметы с определёнными весами и ценностями, а также максимальная вместимость рюкзака. Необходимо найти максимальную суммарную ценность предметов, не превышая вместимость. Каждый предмет можно взять не более одного раза.
- Какова сложность Задача о рюкзаке 0/1 (0/1 Knapsack Problem)?
- Время (среднее): O(n × W) · Память: O(n × W)
- Для кого предназначена визуализация Задача о рюкзаке 0/1 (0/1 Knapsack Problem)?
- Визуализация Задача о рюкзаке 0/1 (0/1 Knapsack Problem) рассчитана на продвинутый уровень в категории «Динамическое программирование». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Задача о рюкзаке 0/1 (0/1 Knapsack Problem)?
- В той же категории (Динамическое программирование) вы можете изучить: Fibonacci DP, Longest Common Subsequence. Каждый из них имеет интерактивную визуализацию.