Восстановление ответа в ДП

ДП посчитало «лучшую ценность» или «минимум монет» — но как вывести сам набор? Учимся восстанавливать решение, а не только его стоимость.

Восстановление ответа — приём, при котором по заполненной таблице ДП мы реконструируем не только оптимальное значение, но и сам объект (набор предметов, последовательность шагов), который его достигает.

Зачем это нужно

Очень часто задача просит не число, а сам ответ: «выведите минимальный набор монет», «какие предметы взять», «восстановите путь». Базовое ДП даёт лишь оптимальное значение в финальной ячейке. Чтобы вытащить сам ответ, нужно либо запоминать сделанный выбор в каждом состоянии, либо после заполнения таблицы пройти по ней в обратную сторону, восстанавливая шаги. Это обязательный навык: задач с восстановлением на олимпиадах очень много, и потеря этих баллов обидна.

Два способа восстановления

Обратный проход по таблице. Не храним ничего лишнего; после заполнения идём из финального состояния назад, на каждом шаге определяя, какой переход привёл к текущему значению. Так мы восстанавливали LCS в прошлом уроке.
Хранение выбора. Параллельно с dp ведём массив choice (или parent), где записываем, какое решение дало оптимум в этом состоянии. Потом просто разворачиваем цепочку выборов.

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

Пример 1. Минимум монет + сами монеты

Найдём минимальное число монет для суммы S и выведем сами монеты. dp[s] — минимум монет на сумму s; в parent[s] запомним, какой монетой мы «пришли» в это состояние.

coins = [1, 3, 4]
S = 6
INF = float("inf")
dp = [INF] * (S + 1)
parent = [-1] * (S + 1)      # какой монетой достигли суммы s
dp[0] = 0
for s in range(1, S + 1):
    for c in coins:
        if s - c >= 0 and dp[s - c] + 1 < dp[s]:
            dp[s] = dp[s - c] + 1
            parent[s] = c    # запоминаем выбор

# Восстановление: идём от S назад, вычитая запомненные монеты
result = []
s = S
while s > 0:
    c = parent[s]
    result.append(c)
    s -= c
print("Минимум монет:", dp[S])
print("Сами монеты:", sorted(result))

Логика восстановления: в parent[S] лежит последняя добавленная монета; вычитаем её и переходим к parent[s−c], и так до нуля. Для суммы 6 монетами 1,3,4 жадность дала бы 4+1+1 (3 монеты), а ДП находит оптимум 3+3 — всего 2 монеты. Заодно видим, почему здесь нельзя было применить жадность из раздела 2.

Вывод:

Минимум монет: 2
Сами монеты: [3, 3]

Пример 2. Рюкзак: какие предметы взяли

В рюкзаке нас часто просят перечислить выбранные предметы. Здесь удобен обратный проход по двумерной таблице: если dp[i][cap] != dp[i−1][cap], значит предмет i был взят.

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
W = 8
n = len(weights)

dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = weights[i - 1], values[i - 1]
    for cap in range(W + 1):
        dp[i][cap] = dp[i - 1][cap]
        if cap >= w:
            dp[i][cap] = max(dp[i][cap], v + dp[i - 1][cap - w])

# Восстановление: идём от dp[n][W] назад по предметам
chosen = []
cap = W
for i in range(n, 0, -1):
    if dp[i][cap] != dp[i - 1][cap]:     # значение изменилось => предмет i взят
        chosen.append(i - 1)             # индекс предмета
        cap -= weights[i - 1]            # уменьшаем остаток вместимости
chosen.reverse()
print("Максимальная ценность:", dp[n][W])
print("Взяты предметы (индексы):", chosen)
print("Их веса:", [weights[i] for i in chosen],
      "ценности:", [values[i] for i in chosen])

Идём с конца: для предмета i сравниваем dp[i][cap] и dp[i−1][cap]. Если они различны — значит, оптимум на этом шаге достигался именно взятием предмета i; добавляем его и уменьшаем вместимость. Получаем предметы с весами 3 и 5 (ценности 4 и 6) — суммарная ценность 10, как мы и считали в уроке о рюкзаке.

Вывод:

Максимальная ценность: 10
Взяты предметы (индексы): [1, 3]
Их веса: [3, 5] ценности: [4, 6]

Общий рецепт восстановления

Определи финальное состояние (откуда начинать обратный ход) — обычно ячейка с ответом.
На каждом шаге пойми, какой переход привёл к текущему значению (либо по parent, либо сравнивая dp соседних состояний).
Сделай шаг назад в это предыдущее состояние, записав сделанный выбор.
Повтори до базового состояния; разверни накопленный список, если шёл с конца.

Подводные камни

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

Итог

Базовое ДП даёт значение оптимума; чтобы вывести сам ответ, нужно восстановление.
Два способа: хранить массив выбора (parent/choice) или идти по таблице назад, определяя переход.
Рецепт: старт из финальной ячейки → определить переход → шаг назад → до базы → развернуть.
Одномерная оптимизация памяти мешает восстановлению — храни нужную информацию заранее.