dynamic-programming
Проблема с рюкзаком

замечания

0-1 Проблема с рюкзаком

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

Давайте пока сосредоточимся на нашей проблеме. Например, допустим, у нас есть емкость для ранца 7 . У нас есть 4 предмета. Их веса и ценности:

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

Один метод грубой силы будет принимать все возможные комбинации предметов. Затем мы можем рассчитать их общий вес и исключить их, которые превышают емкость нашего рюкзака и узнают тот, который дает нам максимальную ценность. Для 4 предметов нам нужно будет проверить ( 4! - 1 ) = 23 возможных комбинаций (исключая один без элементов). Это довольно громоздко, когда количество предметов увеличивается. Здесь несколько аспектов, которые мы можем заметить, это:

• Мы можем брать меньше предметов и вычислять максимальное значение, которое мы можем получить, используя эти элементы и объединяя их. Поэтому нашу проблему можно разделить на подзадачи.
• Если мы вычислим комбинации для элемента {1,2} , мы можем использовать его при вычислении {1, 2, 3} .
• Если мы минимизируем вес и максимизируем значение, мы можем найти наше оптимальное решение.

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

Мы возьмем таблицу 2D-массива, где количество столбцов будет максимальным значением, которое мы можем получить, взяв элементы + 1. И количество строк будет таким же, как количество элементов. Наш массив будет выглядеть так:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

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

Наша первая колонка заполнена 0 . Это означает, что если наша максимальная емкость равна 0 , независимо от того, что у нас есть, поскольку мы не можем выбрать какие-либо предметы, наше максимальное значение будет равно 0 . Начнем с таблицы [0] [1] . Когда мы заполняем Таблицу [1] [1] , мы спрашиваем себя, была ли наша максимальная емкость 1, и у нас был только первый элемент, каково было бы наше максимальное значение? Лучшее, что мы можем сделать, это 1 , выбрав предмет. Для таблицы [0] [2] это означает, что если наша максимальная емкость равна 2 и у нас есть только первый элемент, максимальное значение, которое мы можем получить, равно 1 . Это будет одинаково для таблицы [0] [3] , таблицы [0] [4] , таблицы [0] [5] , таблицы [0] [6] и таблицы [0] [7] . Это потому, что у нас есть только один элемент, который дает нам значение 1 . Поскольку у нас есть только 1 количество каждого предмета, независимо от того, как мы увеличиваем емкость нашего рюкзака, из одного элемента, 1 - это лучшее, что мы можем сделать. Итак, наш массив будет выглядеть так:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Двигаясь дальше, для таблицы [1] [1] , мы спрашиваем себя, были ли у нас пункты 1 и 2, и если максимальная емкость нашего рюкзака равнялась 1 , каково максимальное значение, которое мы можем получить? Если мы возьмем оба пункта 1 и 2 , общий вес будет 4 , что превысит нашу текущую емкость ранца. Поэтому элемент 2 не может быть выбран. Теперь самое лучшее, что мы можем сделать, не взяв пункт 2 ? Значение сверху, то есть Таблица [0] [1], которое содержит максимальное значение, которое мы можем получить, если бы мы имели максимальную емкость 1, и мы не выбрали второй элемент. Для таблицы [1] [2] , поскольку 2 меньше веса [2] , то есть веса второго элемента, мы не можем взять элемент. Таким образом, мы можем установить, что если вес текущего элемента больше нашей максимальной емкости, мы не можем взять этот элемент. В этом случае мы просто возьмем значение сверху, которое представляет максимальное значение, которое мы можем взять, за исключением элемента.

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

Теперь для таблицы [1] [3], так как наша максимальная емкость равна нашему текущему весу, у нас есть два варианта.

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

Среди двух вариантов мы выберем тот, из которого мы получим максимальное значение. Если мы выберем элемент, мы получим: значение для этого элемента + максимальное значение из остальных элементов после принятия этого элемента = 4 + 0 = 4 . Мы получаем 4 (значение элемента) из нашего весового массива, а 0 (максимальное значение, которое мы можем получить из остальной части предметов после взятия этого предмета), поступает на 1 шаг выше и 3 шага назад. Это таблица [0] [0] . Зачем? Если мы возьмем предмет, оставшаяся емкость будет 3 - 3 = 0, а оставшийся элемент будет первым. Хорошо, если вы вспомните, что Таблица [0] [0] хранит максимальное значение, которое мы можем получить, если наша емкость равна 0, и у нас был только первый элемент. Теперь, если мы не выберем элемент, максимальное значение, которое мы можем получить, исходит от 1 шага выше, то есть 1 . Теперь мы берем максимум этих двух значений ( 4 , 1 ) и устанавливаем таблицу [1] [2] = 4 . Для таблицы [1] [4] , с 4 , максимальная емкость ранца больше 3 , вес нашего текущего элемента, мы снова имеем два варианта. Мы принимаем max ( Вес [2] + Таблица [0] [4-Вес [2]] , Таблица [0] [4] ) = max ( Вес [2] + Таблица [0] [1] , Таблица [0] [4] ) = max ( 4 + 1 , 1 ) = 5 .

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

Используя эти две формулы, мы можем заполнить весь массив таблиц . Наш массив будет выглядеть так:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

Здесь последнее значение, которое мы ввели в наш массив, Таблица [3] [7] содержит наше требуемое максимальное значение. Это максимальное значение, которое мы можем получить, если у нас было 4 предмета, а максимальная емкость рюкзака - 7 .

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

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

O(n*maxCapacity) сложность этого алгоритма - O(n*maxCapacity) , где n - количество элементов, а maxCapacity - максимальная емкость нашего рюкзака.

До сих пор мы нашли максимальное значение, которое мы можем получить из нашего примера. Остается один вопрос. Каковы фактические предметы? Мы восстановим значения в нашем массиве Table, чтобы узнать, какие элементы мы взяли. Мы будем следовать двум стратегиям:

• Для любого элемента, если значение исходит из позиции выше, мы не берем текущий элемент. Мы переходим на 1 шаг выше.
• Если значение не идет с позиции выше, мы взяли элемент. Итак, мы переходим на 1 шаг выше и х шаг назад, где x - вес текущего элемента.

Псевдокод будет:

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

Если мы повторим наш пример, мы получим:

Из этого можно сказать, что мы можем взять пункты 2 и 3, чтобы получить максимальное значение.