Эта история является прямым продолжением моей предыдущей публикации о Жадных алгоритмах, так что вы можете сначала проверить это. Это нормально, если вас интересует только Динамическое программирование и вы хотите пропустить его, поскольку я снова буду объяснять проблему.

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

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

В отличие от предыдущего поста, на этот раз мы поговорим о задаче 0–1 о рюкзаке. Будучи участником восстания против социальной несправедливости в политике правительства, вы решили объединиться с некоторыми из своих друзей-ботаников, чтобы выполнить работу в банке. Каждый член банды несет мешок вместимостью 50 кг. Каждый из вас попадает в хранилище один за другим, и когда, наконец, приходит ваша очередь, вы видите, что осталось взять только один золотой, один серебряный и один платиновый слиток. Вы хотите максимально увеличить свой прирост с вашей ограниченной грузоподъемностью.

  • золотой слиток весит 20 кг и стоит 1000 долларов.
  • Серебряный слиток весит 30 кг и стоит 1200 долларов.
  • Платиновый слиток весит 10 кг и стоит 600 долларов.

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

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

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

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

Серия Фибоначчи

Ух, это снова ... В старшей школе я помню, как меня очень впечатлили теории Золотого сечения Древней Греции. После 10 лет в информатике я смотрю на ряды Фибоначчи свысока. Тем не менее, это весьма полезно, когда вы хотите поговорить о рекурсии. Вот формула:

Ряд Фибоначчи реализован простой рекурсивной функцией:

unsigned int fibonacci(unsigned int n) {
    if (n < 2) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Легко… Эта короткая функция решает ряды Фибоначчи, но у этого подхода есть проблема. Вы можете это заметить? Давай, подумай немного.

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

Но зачем тебе это? Зачем вам нужно вычислять один и тот же результат снова и снова? Я имею в виду, это просто глупо. Вместо этого почему бы не сохранить результат для fibonacci (x) и просто использовать это значение, когда оно вам снова понадобится? А теперь хлопните себя по лицу и кричите динамическое программирование!

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

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

// Note: Size is n + 1 because we store the values from 0 to n
unsigned int lookup[n + 1] = {0};
unsigned int fibonacci(unsigned int n) {
    if (n < 2) {
        return n;
    } else if (lookup[n] != 0) {
        return lookup[n];
    }
    lookup[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return lookup[n];
}

Все, что мы изменили в коде, - это ввести поисковый массив и вернуть сохраненное значение, если такое существует. Далее мы видим восходящий подход, который превращает алгоритм в итеративную функцию.

unsigned int fibonacci(unsigned int n) {
    unsigned int lookup[n + 1] = {0};
    lookup[0] = 0;
    lookup[1] = 1;
    for (unsigned int i = 2; i <= n; i++) {
        lookup[i] = lookup[i - 1] + lookup[i - 2];
    }
    return lookup[i];
}

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

Теперь вернемся к задаче о рюкзаке. Мы уже видели, что нам нужно перебрать все возможности, чтобы найти оптимальное решение. Как и в случае с рядами Фибоначчи, мы будем использовать метод «разделяй и властвуй», рекурсивно решая задачу для пакетов меньшего размера.

Рекурсивный алгоритм для задачи о рюкзаке 0–1 немного сложнее, поэтому позвольте мне сначала уточнить. Функция имеет 3 параметра:

  • vector ‹Item› элементы: список элементов, ожидающих отправки.
  • int size: Остающийся размер (вес) сумки.
  • int index: индекс последнего обработанного элемента в элементах

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

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

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

  • В сумке больше нет места
  • Все товары уже обработаны

Окончательный код C ++ выглядит примерно так:

int knapsack(vector<Item> items, int size, int index) {
    // Base case: either bag is full or we tried all items
    if (size == 0 || index == items.size()) {
        return 0;
    }
    // Current item weighs more than the remaining bag size
    Item current = items[index];    
    if (current.weight > size) {
        return knapsack(items, size, index + 1);
    }
    int weight = current.weight;
    int price = current.price;
    // a is the price when current item is taken
    // b is when it is not taken
    int a = price + knapsack(items, size - weight, index + 1);
    int b = knapsack(items, weight, index + 1);
    return max(a, b);
}

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

Это всего лишь рекурсивное решение, которое выполняет повторяющиеся вычисления, как когда-то выполняла наша функция Фибоначчи. Чтобы этого избежать, нам нужно сохранить уже рассчитанные результаты в 2D-массиве.

Самая сложная часть этого алгоритма - как сохранить результаты. Элемент lookupTable [i] [j] соответствует результату для первых i единиц, обработанных для мешка вместимостью j кг. Вы собираетесь прочитать это предложение несколько раз.

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

// Note: This is not valid in C++ but you got the point
int lookupTable[count + 1][size + 1] = {-1};
int knapsack(vector<Item> items, int size, int index) {
    // Base case: either bag is full or we tried all items
    if (size == 0 ||index == items.size()) {
        return 0;
    }
    // Result already calculated
    if (lookupTable[index][size] != -1) {
        return lookupTable[index][size];
    }
    // Current item weighs more than the remaining bag size
    Item current = items[index];    
    if (current.weight > size) {
        lookupTable[index][size] = knapsack(items, size, index + 1);
        return lookupTable[index][size];    
    }
    int weight = current.weight;
    int price = current.price;
    // a is the price when current item is taken
    // b is when it is not taken
    int a = price + knapsack(items, size - weight, index + 1);
    int b = knapsack(items, weight, index + 1);
    
    lookupTable[index][size] = max(a, b);    
    return lookupTable[index][size];
}

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

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

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

На данном этапе это бесполезно, да? Что ж, до встречи в следующей части ...