Задача о рюкзаке динамическое программирование python

Рассмотрим рюкзак (или В вашем распоряжении есть набор предметов. Каждый из которых имеет разную ценность и вес. Вы хотите наполнить рюкзак самой ценной комбинацией предметов. Не перегружая его и не выходя за пределы допустимого веса. Это проблема Рюкзака. Это одна из наиболее хорошо изученных задач комбинаторной оптимизации и популярное введение в динамическое программирование. В этом посте мы объясним два варианта проблемы рюкзака:

  1. Элементы могут быть выбраны повторно (вариация продуктового магазина)
  2. Предметы можно выбрать не более одного раза (музейная вариация)

Прежде чем мы погрузимся, давайте сначала кратко поговорим о том. Что влечет за собой динамическое программирование.

Объезд: Краткое введение в динамическое программирование

Возможно, вы слышали термин По своей сути динамическое программирование-это метод проектирования алгоритмов. Который включает в себя выявление подзадач в рамках общей задачи и их решение. Начиная с самой маленькой. Результаты более мелких подзадач запоминаютсяили сохраняются для последующего использования последующими более крупными подзадачами. Рассмотрим следующий массив, A:

Скажем, мы хотим сделать префиксную сумму по всему массиву. И нас особенно интересует элемент 4 (выделен красным).

Достаточно просто, просто повторите цикл и сложите значения перед ним. Теперь предположим. Что мы хотим знать префикс sum до элемента 5. А как насчет элемента 2? Нужно ли нам снова перебирать их все для каждого из них? Используя динамическое программирование. Мы можем сделать это немного более эффективно. Используя дополнительный массив T для запоминания промежуточных значений.

Пусть T[i] — сумма префиксов в элементе i. Тогда мы можем сказать, что T[i] = T[i-1] + A[i]. Здесь T[i-1] представляет меньшую подзадачу-все индексы, предшествующие текущему.

Теперь посмотрите на массив T ниже чтобы помочь визуализировать это:

Это был довольно простой пример динамического программирования. Но мы будем использовать те же самые мыслительные процессы и методы для решения проблемы рюкзака. А теперь вернемся к нашим регулярным программам…


Проблема Рюкзака Переформулирована

Давайте на этот раз сформулируем проблему несколько более формально. У нас есть следующее:

  • Рюкзак, который может вместить общий вес W
  • Коллекция из n предметов на выбор
  • Каждый из этих n элементов имеет вес w, который может быть выбран из массива w1…wn
  • Каждый из этих n элементов имеет значение v, которое может быть выбрано из массива v1…vn

Мы хотим выбрать оптимальную комбинацию предметов из таких. Чтобы максимизировать общую стоимость наших предметов. Не превышая максимального предела веса W.

Наш рюкзак и вещи

Ради решения нижеприведенных задач мы рассмотрим следующий рюкзак и коллекцию предметов:

Рюкзак: W = 15
Предметов:

Предмет Вес Ценность
1 2 1
2 10 20
3 3 3
4 6 14
5 18 100

Повторный Выбор (Вариант Продуктового магазина)

Первая вариация задачи о ранце позволяет нам многократно выбирать один и тот же предмет и класть его в сумку. Я называю этот вариант о зачистке супермаркета, где участники наперегонки заполняют корзину максимально ценными товарами. Поскольку в продуктовом магазине есть много доступных товаров. Вполне нормально выбрать один и тот же товар несколько раз.

Определите нашу подзадачу

Сначала определим нашу подзадачу. Пусть w-вес меньше нашего максимального веса W. Или, другими словами, 0 ≤ wW. Учитывая это. Мы можем определить нашу подзадачу как:

K(w) = максимальное значение. Достижимое при общем весе ≤ w

Таким образом, в основном. Каждая подзадача будет работать на меньшем и меньшем пределе веса. И мы попробуем наши товары. Доступные против этого меньшего предела.

Определите наше Повторение

Базовый случай: K(0) = 0
Повторение: K(w) = max( for(in) { K(wwi) + vi, если wiw } )

То, что мы делаем здесь. — это пробуем все возможности для добавления элементов при факторинге снижения веса. Понесенного этим элементом. Мы используем функцию max (), чтобы убедиться. Что мы выбираем параметры подзадачи. Которые дают наибольшее значение. Наш базовый случай-K(0), дающий значение 0, потому что ни один элемент не имеет веса ≤ 0.

Структура таблицы мемуаризации

Для этой задачи мы должны иметь возможность использовать простую 1-мерную таблицу (массив) длиной от w1 до W. В каждом индексе этой таблицы мы будем хранить максимальное значение. Доступное при этом суб-весе. И поскольку мы можем выбирать одни и те же элементы несколько раз. Нам не нужно хранить какую-либо информацию о выбранных элементах.

Реализация Python

Ниже приведен пример реализации на Python. Не стесняйтесь настраивать значения для элементов и W, чтобы увидеть. Что произойдет!

Анализ времени выполнения

Давайте взглянем на сложный бит кода выше и определим. Что это большая верхняя граница O.

for w in range(1, W + 1): max_sub_result = 0 for i in range(1, n): wi = item_weights[i] vi = item_values[i] if wi  w: subproblem_value = K[w - wi] + vi if subproblem_value > max_sub_result: max_sub_result = subproblem_value K[w] = max_sub_result 

В пределах внешнего цикла над весами W у нас есть вложенный цикл над n элементами. В этих циклах сравнения и поиски из K[] занимают постоянное время. Это означает, что в нашем алгоритме преобладают вложенные циклы. Поэтому он является O(nW) во временной сложности.


Единичный выбор (Музейный Вариант)

Первая вариация задачи о рюкзаке позволяет выбрать предмет не более одного раза. Я называю это Здесь есть только один из каждого предмета, поэтому мы. Даже если есть предмет. Который весит 1 фунт и стоит больше всего. Можем поместить его в наш рюкзак только один раз.

Определите нашу Подзадачу

Наш подход здесь будет очень похож на вариант Так что давайте примем это во внимание при определении нашей подзадачи!

Пусть i-элемент из наших n элементов, такой, что 0 ≤ in.
Кроме того, как и раньше, пусть w-вес меньше нашего максимального веса W. Или, другими словами, 0 ≤ wW.

Учитывая эти условия, мы можем определить нашу подзадачу как:

K(i, w) = максимальное значение. Достижимое с подмножеством объектов в 1,…, i, которые имеют общий вес ≤ w

Определите наше Повторение

Базовый случай 1: K(0, w) = 0
Базовый случай 2: K(i, 0) = 0
Повторение:

Если wiw:
K(i, w) = max(K(i — 1, wwi) + vi, K(i — 1, wwi))
Else:
K(i, w) = K(i — 1, w)

Это повторение немного сложнее, чем предыдущее, поэтому давайте возьмем секунду. Чтобы деконструировать его. Наши базовые случаи-это либо когда мы находимся в пункте 0, который представляет собой пустой набор предметов, либо когда мы находимся в весе 0, где мы больше не можем добавить какой-либо предмет в рюкзак. Так как ни в одном из этих случаев ничего не может быть добавлено. Наше максимальное значение равно 0.

Теперь, что касается повторения, мы сначала должны проверить. Есть ли у нас место для добавления рассматриваемого предмета в рюкзак. Если у нас есть место мы попробуем два варианта:

  1. Добавляем в рюкзак текущий предмет: K(i — 1, wwi) + vi
  2. Мы не добавляем текущий элемент: K(i — 1, wwi)

Мы берем максимальное значение этих двух сценариев через max().

Если предмет не помещается в рюкзак (т. Е. wi > > w), то нет смысла рассматривать. Какую ценность мы могли бы получить от него. И мы просто следуем по пути K(i — 1, wwi).

Структура таблицы запоминания

Поскольку наше определение задачи K(i, w) принимает два параметра. Простого 1-мерного массива будет недостаточно. Нам понадобится 2-мерная таблица с размерами от 0…n и 0…W. В каждом индексе этой таблицы мы будем хранить максимальное значение. Получаемое для каждого элемента i при суб-весе w.

Спойлеры, но для задачи выше окончательная версия этой таблицы будет выглядеть так:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 0 0 1 1 1 1 1 1 1 1 20 20 21 21 21 21
3 0 0 1 3 3 4 4 4 4 4 20 20 21 23 23 24
4 0 0 1 3 3 4 14 14 15 17 20 20 21 23 23 24
5 0 0 1 3 3 4 14 14 15 17 20 20 21 23 23 24

Реализация Python

Ниже приведен пример реализации на Python. Раскомментируйте и запустите код Pandas внизу, чтобы визуализировать 2D-таблицу.

Анализ времени выполнения

Давайте взглянем на сложный фрагмент кода выше и определим. Что это верхняя граница Big O.

for i in range(1, n): for w in range(1, W + 1): wi = item_weights[i] vi = item_values[i] if wi  w: K[i][w] = max([K[i - 1][w - wi] + vi, K[i - 1][w]]) else: K[i][w] = K[i - 1][w] 

Анализ этой проблемы очень похож на то, что мы делали ранее. Внешний цикл над n элементами содержит внутренний цикл над W весами.. В этих циклах сравнения, max ()и поиск из K[][] занимают постоянное время. Это означает, что в нашем алгоритме преобладают вложенные циклы. Поэтому он является O(nW) во временной сложности.


Краткие сведения

Вот он, два варианта проблемы рюкзака с табличными решениями динамического программирования. Надеюсь, вы нашли этот пост полезным. Если нет, то я, по крайней мере, нашел полезным для себя написать его!


Обложка Фото Кредит:
Митчелла Гриста на Unsplash

Мне показалось. Что эта фотография действительно отражает концепцию рюкзаков и таблиц для запоминания. 😂