Перейти к содержанию

14.8   Упражнения

14.8.1   Вопросы для самопроверки

1.   Когда подходит динамическое программирование

Ученик утверждает: «Если можно записать рекуррентное соотношение, нужно использовать динамическое программирование». Для каждой из трех задач выберите наиболее подходящий из трех вариантов: динамическое программирование; поиск с возвратом; цикл или математическая формула без таблицы dp. Укажите одну основную причину.

  1. Набрать сумму 6 с помощью монет номиналов [1, 3, 4], используя каждый номинал любое число раз, и найти минимальное число монет;
  2. вывести все перестановки [1, 2, 3];

  3. вычислить \(1 + 2 + \dots + n\).

    Для задачи, которой подходит динамическое программирование, также объясните значение dp[i].

Ответ

  1. Подходит динамическое программирование. Пусть dp[i] — минимальное число монет, необходимое для получения суммы i. Для каждой монеты c, не превосходящей i, значение dp[i-c] + 1 можно рассматривать как возможный ответ, а затем выбрать минимум среди всех вариантов. Разные последовательности выбора многократно приводят к одной и той же сумме, а оптимальное решение для большей суммы можно составить из оптимальных решений для меньших сумм. Для суммы 6 ответ равен 2: 3 + 3.

  2. Следует использовать поиск с возвратом. Задача требует поочередно получить все 6 перестановок; поиск с возвратом позволяет систематически сделать выбор, продолжить поиск, затем отменить выбор и перейти к другой ветви. Каким бы ни был метод, при фактическом выводе всех перестановок пропустить их перебор нельзя.

  3. Достаточно цикла или формулы суммы арифметической прогрессии. Хотя можно записать S(i) = S(i-1) + i, при вычислении S(i) требуется только одно меньшее значение S(i-1), а каждая частичная сумма вычисляется один раз. Повторяющихся подзадач нет, поэтому таблица dp не нужна. Возможность записать рекуррентное соотношение не означает необходимости динамического программирования.

2.   Как вычислить одну ячейку таблицы рюкзака

Задача о рюкзаке 0-1: веса предметов wgt = [1, 2, 3], их стоимости val = [5, 11, 15], вместимость рюкзака равна 4. dp[i][c] — максимальная стоимость, которую можно получить, рассматривая только первые \(i\) предметов при предельной вместимости рюкзака \(c\); заполнять рюкзак точно до предела не требуется.

Вычислите только состояние dp[3][4]. Известно, что dp[2][4] = 16 и dp[2][1] = 5.

  1. Какова возможная стоимость, если не брать 3-й предмет?
  2. Какая вместимость останется, если взять 3-й предмет, и чему равна возможная стоимость?
  3. Какое значение нужно присвоить dp[3][4]? Какие предметы ему соответствуют?
Ответ

  1. Если не брать 3-й предмет, сохраняется результат для первых двух предметов, поэтому возможная стоимость равна dp[2][4] = 16.

  2. Вес 3-го предмета равен 3, после его добавления остается вместимость \(4-3=1\). Возможная стоимость равна dp[2][1] + 15 = 5 + 15 = 20.

  3. Сравнив 16 и 20, получаем dp[3][4] = 20. Это соответствует выбору 1-го и 3-го предметов: их общий вес равен \(1+3=4\), а общая стоимость — \(5+15=20\).

    Вычисление этого состояния показывает один выбор в задаче о рюкзаке 0-1: «взять или не взять».

3.   В каком порядке обновлять вместимость рюкзака

В задаче о рюкзаке 0-1 есть только один предмет весом 2 и стоимостью 5; вместимость рюкзака равна 4. Каждый предмет разрешено выбрать не более одного раза, а исходный одномерный массив имеет вид dp = [0, 0, 0, 0, 0].

Обрабатывая предмет, ученик обновляет вместимость от 2 до 4:

  • после обновления dp[2] получается 5;
  • после обновления dp[3] также получается 5;
  • при обновлении dp[4] снова используется только что полученное dp[2], поэтому выходит dp[4] = 10.
  1. Правилен ли результат dp[4] = 10? Почему?
  2. Чему должно быть равно dp[4], если каждый предмет можно выбрать не более одного раза?
  3. При обработке каждого предмета вместимость нужно перебирать от большей к меньшей или от меньшей к большей? Какую проблему предотвращает такой порядок?
Ответ

  1. Результат неверен. Стоимость 10 означает, что предмет стоимостью 5 положили в рюкзак дважды, нарушив условие «каждый предмет можно выбрать не более одного раза».

  2. В рюкзак можно положить не более одного такого предмета, поэтому правильное значение dp[4] равно 5.

  3. Вместимость нужно обновлять от большей к меньшей, то есть в порядке 4, 3, 2. Тогда при вычислении dp[c] читаемое значение dp[c-2] все еще относится к состоянию до обработки текущего предмета, и этот предмет нельзя повторно использовать на той же итерации.

14.8.2   Задачи по программированию

1.   Число способов подняться по лестнице

Лестница состоит из n ступеней. За один шаг можно подняться только на 1 или 2 ступени, причем нужно попасть точно на ступень n. Вычислите число различных способов подъема. Считайте, что n >= 1; способы различаются только последовательностью шагов на 1 и 2 ступени. Используйте одномерный массив динамического программирования; пока не применяйте оптимизацию памяти, сохраняющую лишь два состояния.

Подсказки
  1. Последний шаг на ступень i мог быть только на 1 или на 2 ступени
  2. Поэтому dp[i] = dp[i-1] + dp[i-2]
  3. Сначала обработайте случаи n, равного 1 и 2, а затем заполняйте таблицу начиная с 3-й ступени

LeetCode

2.   Рюкзак 0-1

Даны массивы одинаковой длины wgt и val: вес предмета i — положительное целое число wgt[i], а его стоимость — неотрицательное целое число val[i]. Вместимость рюкзака cap — неотрицательное целое число. Каждый предмет можно выбрать не более одного раза. Найдите максимальную суммарную стоимость предметов, общий вес которых не превышает cap. Используйте одномерное динамическое программирование.

Подсказки
  1. Создайте массив dp длины cap + 1, где dp[c] — максимальная стоимость при предельной вместимости c
  2. Обрабатывая предмет i, сравните dp[c] для варианта «не брать предмет» и dp[c-wgt[i]] + val[i] для варианта «взять предмет»
  3. Вместимость нужно обновлять от большей к меньшей, чтобы не выбрать текущий предмет повторно на одной итерации
Оставляйте свои идеи, вопросы и предложения в комментариях