8.6. Задача о рюкзаке

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

Естественная «жадная» стратегия — взять самый тяжелый слиток, на который хватает вместимости рюкзака, и повторно проверить, а осталось ли место на ещё один слиток.

При наборе слитков, приведённом выше, и рюкзаке вместимостью «жадный» алгоритм выбирает слитки весом и . Однако оптимальное решение — использовать слитки весом 4, 6 и 10!

• Входные данные: Первая строка ввода содержит целое число (вместимость рюкзака) и количество золотых слитков . В следующей строке приведены целых чисел , которые определяют вес золотых слитков.
• Выходные данные: Максимальный вес золотых слитков, который можно уместить в рюкзак вместимостью .
• Ограничения: ; ; .

Пример 1

Ввод	Вывод
10 3 1 4 8	9

Сумма веса первого и последнего слитков равна .

Вместо решения изначальной задачи проверим, можно ли выбрать поднабор слитков с общим весом , если имеем слитков весом (мы перешли на отсчёт с нуля)?

✒️ Упражнение:
Продемонстрируйте, как можно использовать это решение для выполнения задачи «Максимальное количество золота».

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

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

В обоих случаях мы свели задачу к практически такой же, но с меньшим количеством слитков и меньшей вместимостью рюкзака. Так, переменная будет иметь значение , если существует возможность заполнить рюкзак с вместимостью первыми слитками, и значение в остальных случаях. Анализ двух вышеприведённых случаев приводит нас к следующему рекуррентному соотношению для :

Обратите внимание, что при второе выражение не имеет смысла.

Кроме того, и для любого .

В целом

Так как значения варьируются между 0 и , а значения — между 0 и , мы имеем переменных. Так как зависит от , мы обрабатываем все переменные в возрастающем порядке . В приведённом ниже псевдокоде мы используем двумерный массив pack размера , а сохраняет значение . Время выполнения данного решения составляет .

Knapsack([w[0],…,w[n−1]],W):
    pack = two-dimensional array of size (W+1)×(n+1)
    initialize all elements of pack to false
    pack[0][0] = true
    for i from 1 to n:
        for w from 0 to W:
            if w[i-1] > w:
                pack[w][i] = pack[w][i−1]
            else:
                pack[w][i]←pack[w][i−1] OR pack[w−w[i−1]][i−1]
    return pack[W][n]

В приведённой ниже двумерной таблице представлены результаты вызова Knapsack([1,3,4], 8. F и T означают значения false и true.

Другое решение будет заключаться в анализе поднаборов всех слитков. Наша цель — найти поднабор из слитков с общим весом . Простой подход к такой задаче — просматривать все поднаборы и проверять, есть ли поднабор с весом . Так как каждый слиток можно или пропустить, или взять, каждый поднабор из трёх слитков, который мы анализируем (, , ), можно представить сине-красным бинарным вектором:

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

Рисунок ниже демонстрирует пути, которые соответствуют всем восьми бинарным векторам с длиной 3.

Теперь мы накладываем все эти восемь путей на одну сетку:

Мы классифицируем узел на сетке как истинный («true») при наличии пути от к на рисунке выше. В других случаях — ложный («false»). Теперь мы можем полностью заполнить рюкзак с вместимостью поднабором из первых слитков, если узел — истинный («true»). Узел будет истинным в случаях, если в него проходит или синее, или красное ребро. То есть, если или истинны. Это наблюдение приводит нас к предыдущему рекуррентному соотношению и к такому же решению с динамическим программированием.

А вот ещё один вариант решения, который основан на мемоизации. Приведённый ниже псевдокод рекурсивно вычисляет рекуррентное соотношение из решения 1:

RecursiveKnapsack([w[0],…,w[n−1]],w,i):
    if i=0 and w=0:
        return true
    else if i=0 and w>0:
        return false
    else if i>0 and w_[i-1]>w:
        return RecursiveKnapsack([w[0],…,w[n−1]],w,i−1)
    else:
        return RecursiveKnapsack([w[0],…,w[n−1]],w,i−1) OR   RecursiveKnapsack([w[0],…,w[n−1]],w−w[i−1],i−1)

Вызов RecursiveKnapsack([w_0, ..., w_{n-1}],W, n) решает задачу, но он сильно замедлен из-за необходимости перевычислять одни и те же значения снова и снова. Чтобы это продемонстрировать, рассмотрим рюкзак с вместимостью и слитков с весом , , . Вызов RecursiveKnapsack([1, 1, 1], 4, 3) создаёт рекурсивное дерево, приведённое ниже — каждый узел показывает значения .

Даже в этом простом примере значение вычисляется дважды. С 20 слитками рекурсивное дерево может достичь гигантских размеров — одно и то же значение может вычисляться миллионы раз.

Во избежание такого рекурсивного взрыва мы «оборачиваем» код мемоизацией с помощью ассоциативного массива , который изначально пуст. Ассоциативный массив — это абстрактный тип данных, в котором хранятся пары . Он поддерживается многими языками программирования и, как правило, реализуется как хеш-таблица или дерево поиска. К примеру, в C++ и Java ассоциативный массив называется картой («map»), а в Python — словарём («dictionary»). В реализации, приведённой ниже, ассоциативный массив используется для хранения логических значений для пар .

MemoizedKnapsack([w[0],…,w[n−1]],pack,w,i):
    if (w,i) is not in pack:
        if i=0 and w=0:
            pack[(w,i)] = true
        else if i=0 and w>0:
            pack[(w,i)] = false
        else if i>0 and w_[i-1]>w:
            pack[(w,i)] = MemoizedKnapsack([w[0],…,w[n−1]],pack,w,i−1)
        else: 
            pack[(w,i)] = MemoizedKnapsack([w[0],…,w[n−1]],pack,w,i−1) OR MemoizedKnapsack([w[0],…,w[n−1]],pack,w−w[i−1],i−1)
    return pack[(w,i)]

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