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

Постановка задачи

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

Анализ

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

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

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

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

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

Самый важный навык, который вы должны развить, чтобы овладеть динамическим программированием, — научиться разделять проблему на подзадачи. Чтобы развить этот навык, вы должны сначала как можно больше практиковаться в задачах типа «разделяй и властвуй» и научиться писать рекуррентные отношения. Когда вы знаете, как разбить проблему на подзадачи, в динамическом программировании нет ничего особенного.

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

Приближаемся к решению

Как уже упоминалось, у нас есть два варианта выбора для каждого предмета — мы можем добавить предмет в корзину или не добавлять предмет.

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

Итак, давайте начнем сканирование с последнего элемента, т.е. с n-го элемента. Мы либо включим n-й элемент, либо исключим его.

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

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

Окончательное отношение. Таким образом, окончательное отношение повторения будет таким, как показано ниже.

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