Обновление: Прочтите об оптимизации пространственной сложности решения динамического программирования в моей последующей статье здесь.

Задача о рюкзаке - действительно интересная задача комбинаторики - цитируя Википедию,

«Учитывая набор элементов, каждый с весом и значением, определите количество каждого элемента, который нужно включить в коллекцию, чтобы общий вес был меньше или равнялся заданному пределу, а общее значение было как можно большим. ”

Из Википедии мы видим, что существует несколько вариантов задачи о ранце: рюкзак 0–1, ограниченный рюкзак и неограниченный рюкзак. Сегодня мы сосредоточимся на наиболее распространенном (и простейшем) варианте: задаче о рюкзаке 0–1.

Чуть более интересная и понятная формулировка задачи о рюкзаке 0–1:

Представьте, что вор входит в дом, чтобы ограбить, и несет рюкзак. В доме есть фиксированное количество предметов - каждый со своим весом и ценностью - Ювелирные изделия, с меньшим весом и наибольшей ценностью, по сравнению со столами, с меньшей ценностью, но намного тяжелее. Чтобы подлить масла в огонь, у вора есть старый рюкзак, вместимость которого ограничена. Очевидно, он не может разделить стол пополам или украшения на 3/4. Он либо берет, либо оставляет. "Источник"

К сожалению, мне было трудно понять некоторые части статьи о Hackerearth, поэтому я решил написать свою собственную статью. Эта статья будет в значительной степени основана на статье Hackerearth, а фрагменты кода написаны на Java. Я буду прибегать к дополнительным объяснениям и уточнениям там, где я считаю их необходимыми.

Динамическое программирование

Решим эту проблему с помощью динамического программирования. Для динамического программирования требуется оптимальная подструктура и перекрывающиеся подзадачи, обе из которых присутствуют в задаче о рюкзаке 0–1, как мы увидим ниже.

Хорошо, если вы не понимаете, что такое «оптимальная подструктура» и «перекрывающиеся подзадачи» (это статья на другой день). По сути, это просто означает определенный вид проблем, которые позволяют нам повторно использовать предыдущие решения для более мелких проблем, чтобы вычислить решение текущей проблемы. Вы скоро поймете, что я имею в виду.

Детали проблемы

Предположим, у нас есть рюкзак, вмещающий int w = 10 весовых единиц. У нас есть всего int n = 4 элементов на выбор, значения которых представлены массивом int[] val = {10, 40, 30, 50}, а веса представлены массивом int[] wt = {5, 4, 6, 3}.

Поскольку это задача о рюкзаке 0–1, мы можем либо включить элемент в наш рюкзак, либо исключить его, но не включать часть его, или включить его несколько раз. .

Решение

Шаг 1:

Сначала мы создаем двумерный массив (т.е. таблицу) из n + 1 строк и w + 1 столбцов.

Номер строки i представляет набор всех элементов из строк 1 - i. Например, значения в строке 3 предполагают, что у нас есть только элементы 1, 2 и 3.

Номер столбца j представляет грузоподъемность нашего ранца. Поэтому значения в столбце 5, например, предполагают, что наш рюкзак может вмещать 5 единиц веса.

Собирая все вместе, запись в строке i, столбце j представляет максимальное значение, которое может быть получено с элементами 1, 2, 3… i в рюкзаке, вмещающем j единиц веса.

Назовем нашу таблицу mat матрицей. Следовательно, int[][] mat = new int[n + 1][w + 1].

Шаг 2:

Мы можем немедленно начать заполнение некоторых записей в нашей таблице: базовых случаев, для которых решение тривиально. Например, в строке 0, когда у нас нет предметов для выбора, максимальное значение, которое может быть сохранено в любом рюкзаке, должно быть 0. Аналогично, в столбце 0 для ранца, который может содержать 0 единиц веса, максимальное значение, которое может быть сохранено в нем, равно 0. (Мы предполагаем, что не существует безмассовых ценных предметов.)

Мы можем сделать это с помощью 2 циклов for:

Шаг 3 (суть проблемы):

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

Сначала я опишу логику, а затем приведу конкретный пример.

Связь между значением в строке i, столбце j и значениями предыдущих подзадач следующая:

Напомним, что в строке i и столбце j мы решаем подзадачу, состоящую из пунктов 1, 2, 3… i с помощью рюкзак вместимостью j. На данный момент есть 2 варианта: мы можем либо включить элемент i, либо нет. Следовательно, нам нужно сравнить максимальное значение, которое мы можем получить с элементом i и без него.

Максимальное значение, которое мы можем получить без элемента i, можно найти в строке i-1, столбце j. Эта часть проста. Рассуждения просты: любое максимальное значение, которое мы можем получить с элементами 1, 2, 3… i, очевидно, должно быть таким же максимальным значением, которое мы можем получить с элементами 1, 2, 3… i - 1, если мы решим не включать элемент i.

Чтобы вычислить максимальное значение, которое мы можем получить с элементом i, нам сначала нужно сравнить вес элемента i с грузоподъемностью рюкзака. Очевидно, что если предмет i весит больше, чем может вместить рюкзак, мы не можем его включить, поэтому нет смысла выполнять вычисления. В этом случае решением этой проблемы является просто максимальное значение, которое мы можем получить без элемента i (т.е. значение в строке выше, в том же столбце).

Однако предположим, что предмет i весит меньше, чем вместимость ранца. Таким образом, у нас есть возможность включить его, если он потенциально увеличивает максимально возможное значение. Таким образом, максимальное значение, которое можно получить, включив элемент i, равно значению самого элемента i + максимальное значение, которое может быть получено с оставшейся емкостью рюкзака. Очевидно, мы хотим полностью использовать вместимость нашего рюкзака и не допустить, чтобы оставшаяся вместимость была потрачена впустую.

Следовательно, в строке i и столбце j (который представляет максимальное значение, которое мы можем получить там), мы бы выбрали либо максимальное значение, которое мы можем получить без элемента i, или максимальное значение, которое мы можем получить с элементом i, в зависимости от того, что больше .

Вот конкретный пример того, что я имею в виду.

В строке 3 (элемент 2) и столбце 5 (вместимость ранца 4) мы можем выбрать, включать ли элемент 2 (который весит 4 единицы) или нет. Если мы решим не включать его, максимальное значение, которое мы можем получить, будет таким же, как если бы у нас был только элемент 1 на выбор (который находится в строке выше, то есть 0). Если мы хотим включить элемент 2, максимальное значение, которое мы можем получить с помощью элемента 2, - это значение элемента 2 (40) + максимальное значение, которое мы можем получить с оставшейся емкостью (это 0, потому что рюкзак уже полностью заполнен) .

В строке 3 (элемент 2) и столбце 10 (вместимость ранца 9) мы снова можем выбрать, включать ли элемент 2 или нет. Если мы решим не делать этого, максимальное значение, которое мы можем получить, будет таким же, как и в строке выше в том же столбце, то есть 10 (путем включения только элемента 1, который имеет значение 10). Если мы включим пункт 2, у нас останется оставшаяся вместимость рюкзака 9 - 4 = 5. Максимальное значение, которое может быть получено при вместимости 5, можно найти, посмотрев на строку выше в столбце 5. Таким образом, максимальное значение значение, которое мы можем получить, включив элемент 2, составляет 40 (значение элемента 2) + 10 = 50.

Мы выбираем большее из 50 против 10, и поэтому максимальное значение, которое мы можем получить с помощью пунктов 1 и 2 при вместимости ранца 9, составляет 50.

Алгоритм можно выразить на Java так:

Шаг 4 (окончательное решение):

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

return mat[n][w];

Рабочий код:

Примечание: здесь я напечатал окончательный ответ вместо того, чтобы возвращать его, поскольку все размещено в public static void main.

Спасибо за прочтение!