Рюкзак 0/1 и оптимизация памяти
Выведите рекуррентную формулу для рюкзака 0/1, заполните двумерную таблицу, а затем сократите её до одномерного массива, перебирая вместимость в обратном порядке
«Рюкзак 0/1 и оптимизация памяти» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Задача о рюкзаке 0/1
Задача о рюкзаке 0/1: даны n элементов, каждый из которых имеет вес w[i] и ценность v[i], а также рюкзак вместимостью W. Выберите элементы так, чтобы максимизировать их суммарную ценность, не превышая вместимость. Каждый элемент выбирается ровно один раз (0 = не брать, 1 = брать). Это классический пример из большого семейства задач DP на собеседованиях, включая разбиение на подмножества с равными суммами и сумму с заданным значением.
Состояние DP и рекуррентное соотношение
Определим dp[i][c] как максимальную ценность, которую можно получить, используя первые i элементов при вместимости c. Для элемента i есть два варианта: не брать его (dp[i-1][c]) или взять его, если w[i] <= c (dp[i-1][c-w[i]] + v[i]). Рекуррентное соотношение имеет вид: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]), если w[i] <= c; в противном случае dp[i][c] = dp[i-1][c]. Базовый случай: dp[0][c] = 0 для любого c.
Реализация двумерной таблицы DP
Двумерная таблица содержит (n+1) x (W+1) элементов и заполняется построчно для каждого элемента. После заполнения всех строк в dp[n][W] находится максимальная ценность. Алгоритм работает за O(n × W) времени и использует O(n × W) памяти — это псевдополиномиальная сложность, эффективная при небольшом значении W.
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 10Почему в одномерном DP вместимость перебирается в обратном порядке
Ключевое наблюдение: строка i зависит только от строки i-1. Поэтому можно использовать один одномерный массив и обновлять его на месте. Однако если перебирать вместимость c слева направо (от меньшей к большей), элемент i может быть посчитан дважды: для c-w[i] можно использовать уже обновлённое значение, которое уже включает элемент i. Перебор справа налево (от большей вместимости к меньшей) гарантирует, что каждый элемент будет использован не более одного раза за обновление строки.
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous rowОдномерная реализация с оптимизацией памяти
Если оставить только один массив и перебирать вместимость от W до w[i], можно получить тот же результат, что и с двумерной таблицей, используя O(W) памяти. Сложность по времени остаётся равной O(n × W). Эту оптимизацию памяти особенно важно запомнить: на собеседованиях часто просят свести двумерную задачу о рюкзаке к одномерной.
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10Восстановление выбранных элементов
Чтобы определить элементы со статусом selected, нужна полная двумерная таблица. После её заполнения начните с dp[n][W] и двигайтесь назад: если dp[i][c] != dp[i-1][c], элемент i был включён — вычтите его вес из c и перейдите к строке i-1. Продолжайте, пока i = 0. Одномерная оптимизация лишает нас возможности восстановить выбранные элементы.
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))Практический пример: максимизация общей ценности
Рассмотрим элементы: weights=[2,3,4,5], values=[3,4,5,6], W=8. Оптимальный вариант: взять элементы с весом 3 (ценность 4) и весом 5 (ценность 6) — общий вес равен 8, ценность — 10. Можно также взять элементы с весом 2 и 5 — общая ценность будет равна 9. Или элементы с весом 2 и 3 — ценность 7. DP правильно находит максимум 10. Обратите внимание: жадный подход (сначала взять элемент с наибольшим отношением ценности к весу) выбрал бы элемент с отношением 1.5 (вес 2, ценность 3), что не всегда оптимально.
Дробный рюкзак и рюкзак 0/1
В задаче о дробном рюкзаке можно брать части элементов. Её можно решить жадным алгоритмом, отсортировав элементы по отношению ценности к весу. В задаче о рюкзаке 0/1 элементы неделимы — жадный подход не работает, поэтому требуется DP. Интервьюеры используют это различие, чтобы проверить, знаете ли Вы, когда применим жадный алгоритм. Если Вас спрашивают о дробном варианте, сразу упомяните жадный алгоритм с сортировкой; если речь идёт о варианте 0/1, используйте DP.
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))Псевдополиномиальная временная сложность
Задача о рюкзаке 0/1 является NP-полной, однако мы решаем её за O(nW). Противоречие объясняется тем, что O(nW) — это псевдополиномиальная сложность: W — значение, а не размер входных данных. Двоичное представление W занимает O(log W) битов, поэтому истинная сложность равна O(n × 2^(log W)), то есть является экспоненциальной относительно размера входных данных. Когда W невелико (например, 10⁴), DP применима на практике; когда W может достигать 10⁹, нужны другие подходы.
Дополнительный вопрос на собеседовании: большая вместимость
Если интервьюер ограничивает W очень большим значением (например, 10⁹), а n невелико, стандартный DP перестаёт работать. Возможные альтернативы: (1) метод встречи посередине со сложностью O(2^(n/2) × n), (2) жадное приближение для дробного варианта или (3) метод ветвей и границ. Для большинства задач на собеседованиях с W <= 10⁵ ожидаемым ответом будет одномерный DP с перебором в обратном порядке.
Метод встречи посередине для большой вместимости
Когда W очень велико, а n невелико (например, n=40), стандартный DP со сложностью O(nW) непригоден, но полный перебор 2^n работает слишком медленно. Метод встречи посередине делит элементы на две половины, перебирает все 2^(n/2) подмножеств для каждой половины и оптимально объединяет пары. Одну половину нужно отсортировать по весу, а затем для каждого подмножества другой половины с помощью двоичного поиска найти наилучшее объединение в пределах вместимости. Метод работает за O(2^(n/2) × n) и применим на практике при n до 40.
Быстрая проверка
Проверьте, насколько Вы усвоили понятия из курса «Структуры данных & алгоритмы — подготовка к собеседованию» по этой теме.
Итоги урока
В этом уроке Вы узнали: в DP задачи о рюкзаке 0/1 состояние dp[i][c] представляет максимальную ценность при наличии i элементов и вместимости c, рекуррентное соотношение выбирает, брать или не брать каждый элемент, и одномерная оптимизация памяти перебирает вместимость справа налево, чтобы не считать элементы дважды. Далее мы рассмотрим неограниченный рюкзак, в котором элементы можно использовать повторно, и применим его к задаче о монетах II.
Часто задаваемые вопросы
Урок «Рюкзак 0/1 и оптимизация памяти» бесплатный?
Да — полный текст урока «Рюкзак 0/1 и оптимизация памяти» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Рюкзак 0/1 и оптимизация памяти»?
Выведите рекуррентную формулу для рюкзака 0/1, заполните двумерную таблицу, а затем сократите её до одномерного массива, перебирая вместимость в обратном порядке Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Рюкзак 0/1 и оптимизация памяти»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Рюкзак 0/1 и оптимизация памяти
- Неограниченный рюкзак и размен монет II
- Разбиение на подмножества с равной суммой
- Целевая сумма с положительными и отрицательными знаками