Динамическое программирование (ДП) — это пошаговая стратегия решения задачи. На каждом следующем этапе используются результаты предыдущего. Начать изучение ДП можно с проблемы рюкзака. Исследуем условия задачи и алгоритм поиска ответа.
Что такое задача о рюкзаке
У вас есть набор вещей и рюкзак, где они все точно не поместятся. У каждого предмета есть вес и стоимость. Нельзя делить вещи на части и создавать копии. Требуется собрать рюкзак так, чтобы цена содержимого была максимальной. Нельзя возвращаться за вещами. Каждый предмет можно либо унести и продать, либо навсегда оставить.
Пример условия задачи
Вес и стоимость предметов:
1$ | 8$ | 18$ | 22$ | 28$ |
1 кг | 3 кг | 5 кг | 6 кг | 7 кг |
Вместимость рюкзака: 11 кг.
Проблема ранца (Knapsack Problem) — это задача на комбинаторную оптимизацию. Чтобы найти решение, нужно перебрать все возможные сочетания вещей при укладке рюкзака.
Как работает динамическое программирование
Динамическое программирование работает на основе декомпозиции. Главная задача разбивается на набор простых подзадач. В проблеме рюкзака это составление комбинаций предметов и расчет стоимости. Программа рассматривает варианты решения и выбирает лучший. Результаты каждого действия сохраняются в памяти и используются на следующих этапах алгоритма.
Как решить проблему рюкзака:
- Определить все комбинации грузов.
- Рассчитать стоимость каждого варианта.
- Сравнить варианты решения.
- Найти самое выгодное сочетание.
Программа делит задачу на фрагменты и перебирает все варианты решения. Объем информации наращивается после каждого шага. Эффективная программа решает каждую подзадачу один раз. Чтобы избежать повторов, она сохраняет промежуточные результаты в виде таблицы или в другом формате. Метод помогает решать экспоненциально сложные задачи.
Источник: ru.freepik.com
Как решать задачу о рюкзаке
Правильная алгоритм решения задачи о рюкзаке основана на динамическом программировании. Стратегия решения универсальная. Чтобы записать алгоритм, можно использовать любой язык, с которым вы работаете. Для примера исследуем два варианта записи кода: на Python и на Java.
Алгоритм на Python
Пошаговая инструкция, как решить задачу о ранце:
- Создать таблицу dp размером (n + 1) x (W + 1). В этой таблице n — число предметов, а W — грузоподъемность рюкзака.
- Инициализировать первый столбец и первую строчку таблицы dp нулями.
- Проверить грузы i от 1 до n.
- Проверить общий вес w от 1 до W.
- Если вес груза iw, то dp[i][w] равно максимальному значению dp[i-1][w] и цене i плюс переменная dp[i-1][w-вес груза а i].
- Если условие выше не выполняется, dp[i][w] равно переменной dp[i-1][w].
- Подставляем итоговое значение в правый нижний угол таблицы dp как ответ.
Пример кода на Python:
import timeit
def knapsack(weights, values, capacity):
n = len(weights)
dp = )
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
weights = [1, 3, 5, 6, 7]
values = [1, 8, 18, 22, 28]
capacity = 11
print(timeit.timeit('knapsack(weights, values, capacity)', number=100, globals=globals()))
>>> 0.007788784998410847
Пример использования алгоритма:
weights = [1, 3, 5, 6, 7]
values = [1, 8, 18, 22, 28]
capacity = 11
result = knapsack(weights, values, capacity)
print(result) # Вывод: 11
Алгоритм выбирает предметы весом 5 кг и 6 кг. Общая стоимость груза: 18$ + 22$ = 40$.
Алгоритм на Java
Рассмотрим, как решить аналогичную задачу на Java. Для записи кода возьмем две переменные:
- n — общее количество предметов;
- W — вместимость рюкзака.
Для решения создается таблица с размерностями 0—n и от 0—W. В нее сохраняются результаты выполнения подзадач, чтобы программа их не пересчитывала. Оптимальное решение находится на основе таблицы. В алгоритме используется восходящий подход к работе с данными.
Как записать алгоритм на Java:
int knapsackDP(int[] w, int[] v, int n, int W) {
if (n <= 0 || W <= 0) {
return 0;
}
int[][] m = new int[n + 1][W + 1];
for (int j = 0; j <= W; j++) {
m[0][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (w[i - 1] > j) {
m[i][j] = m[i - 1][j];
} else {
m[i][j] = Math.max(
m[i - 1][j],
m[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
return m[n][W];
}
В коде присутствует вложенный цикл по номеру предмета n и вместимости рюкзака W. Время для обработки алгоритма — O(nW)
Ответ на задачу
Правильный ответ: в рюкзак нужно положить два предмета с ценой 18$ и 22$. Стоимость вещей, которые можно взять с собой, будет максимальной — 40$. Выбранные предметы весят 5 кг и 6 кг, они помещаются в ранец на 11 кг. Грузоподъемность рюкзака используется на 100%.
Источник: ru.freepik.com
Типичные ошибки и как их избежать
Выбор самого дорогого предмета. Задача сформулирована так, что в ранце можно унести одну самую тяжелую и дорогую вещь. Но «очевидный» вариант всегда неправильный.
В примере можно подумать, что нужно взять предмет с весом 7 кг и ценой 28$. Но лучше выбрать две другие вещи:
- с весом 5 кг и ценой 18$;
- с весом 6 кг и ценой 22$.
Стоимость груза: 40$. Выбрав неправильный ответ, вы потеряете 12$.
Поиск решения методом перебора. Начинающие разработчики иногда пытаются решить задачу, перебирая все возможные сочетания. Этот способ занимает много времени и не помогает достичь цели, даже если вы найдете правильный ответ. Задача о рюкзаке придумана, чтобы вы научились использовать динамическое программирование. В некоторых вариантах условия набор предметов бесконечный. Только программа сможет выполнить непрерывную обработку данных.
Рекурсивное решение. Поиск ответа с помощью рекурсии нельзя назвать ошибкой. Но это менее эффективный метод по сравнению с динамическим программированием.
M (n,w) — это эффективное решение для n предметов с ограничением по вместимости рюкзака w.
Чтобы его найти, нужно выбрать максимальное из двух значений:
- эффективное решение для (n-1) предметов при вместимости ранца w (предмет с номером n не учитывается при расчете);
- стоимость n плюс оптимальное решение для (n-1) предметов при вместимости ранца w минус вес n.
Если вес n превышает грузоподъемность ранца, он исключается из возможных вариантов ответа. Эта ситуация относится к первому из описанных случаев.
Как записать решение методом рекурсии на Java:
int knapsackRec(int[] w, int[] v, int n, int W) {
if (n <= 0) {
return 0;
} else if (w[n - 1] > W) {
return knapsackRec(w, v, n - 1, W);
} else {
return Math.max(knapsackRec(w, v, n - 1, W), v[n - 1]
+ knapsackRec(w, v, n - 1, W - w[n - 1]));
}
}
На каждом этапе рекурсии оцениваются два из возможных решений. Время работы рекурсивного алгоритма — O (2 n ).
Главное, что нужно знать
- Динамическое программирование — это пошаговая стратегия решения задачи. На каждом следующем шаге используются данные из предыдущих этапов. Для решения составляется таблица, где сохраняются промежуточные результаты.
- Задача о рюкзаке включает набор предметов и ранец с ограниченной грузоподъемностью. У каждого предмета есть стоимость и масса. Нужно определить, какие вещи взять с собой, чтобы получить максимальную прибыль после продажи.
Чтобы найти самый дорогой набор предметов, нужно перебрать все возможные сочетания. Если сравнивать варианты вручную, это займет очень много времени, и в процессе можно сделать ошибку. Решать задачу нужно с помощью динамического программирования.
