ЕГЭОГЭЕНТ
РУҚА
Задания № 25, 26 · ЕГЭ

Восстановление решения в динамическом программировании

Как по значениям динамической таблицы получить путь, набор действий или сами выбранные элементы
6 мин чтенияСложность: Обновлено 29 сентября 2026

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

Что именно восстанавливают

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

D
Определение

Восстановление решения — построение последовательности состояний и действий, которая приводит из начального состояния в конечное и даёт найденное оптимальное значение.

Например, в задаче о рюкзаке число \(dp[i][w]\) может обозначать максимальную стоимость, которую можно получить из первых \(i\) предметов при вместимости \(w\). Число в последней ячейке сообщает стоимость, но не перечисляет выбранные предметы. Для этого нужно сравнивать ячейку с вариантами, из которых она была получена.

Есть два распространённых способа хранения информации:

  • хранить только таблицу \(dp\) и при восстановлении заново проверять формулы переходов;
  • одновременно хранить массив предков: для каждого состояния записывать предыдущее состояние и выбранное действие.
T
Главное правило

Если состояние \(s\) оптимально и его значение получено переходом из состояния \(p\), то при восстановлении из \(s\) нужно выбрать такое \(p\), для которого формула перехода действительно даёт значение \(dp[s]\). Затем повторять этот шаг до начального состояния.

Обратный ход по таблице

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

\[s_k=s_{final},\qquad s_{j-1}=\operatorname{parent}(s_j),\qquad s_0=s_{start}\]

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

  1. Выбрать конечное состояние и, если нужно, проверить, что оно достижимо.
  2. Определить, какой переход дал значение в текущей ячейке.
  3. Записать выбранный объект, шаг или действие.
  4. Перейти в предыдущую ячейку.
  5. Остановиться в начальном состоянии и развернуть список действий.
Удобная проверка

После восстановления полезно пройти найденную последовательность вперёд от начала и проверить: состояния допустимы, ограничения не нарушены, а итоговое значение совпадает с таблицей.

Пример: рюкзак с восстановлением предметов

Есть \(n\) предметов. У предмета \(i\) масса \(w_i\) и стоимость \(c_i\). Вместимость рюкзака равна \(W\). Каждый предмет можно взять не более одного раза. Требуется получить максимальную стоимость и вывести номера выбранных предметов.

D
Состояние примера

\(dp[i][x]\) — максимальная стоимость, которую можно получить, рассматривая первые \(i\) предметов и используя вместимость не более \(x\).

\[dp[i][x]=\max\left(dp[i-1][x],\;dp[i-1][x-w_i]+c_i\right),\quad x\ge w_i\]

Первый вариант означает «не брать предмет \(i\)», второй — «взять предмет \(i\)». Если \(x<w_i\), предмет взять нельзя, поэтому \(dp[i][x]=dp[i-1][x]\).

Предмет \(i\)Масса \(w_i\)Стоимость \(c_i\)
123
234
345
457

Пусть \(W=7\). После заполнения таблицы получаем максимальную стоимость \(10\): её можно получить, взяв предметы 1 и 4, либо предметы 2 и 3. Покажем восстановление одного из вариантов.

1
Начинаем с конечной ячейки \(dp[4][7]=10\). Проверяем предмет 4: если его взять, значение должно равняться \(dp[3][7-5]+7=dp[3][2]+7=3+7=10\). Равенство выполняется.
\(\displaystyle dp[4][7]=dp[3][2]+c_4=3+7=10\)
2
Значит, предмет 4 выбран. Записываем его номер и переходим в состояние \(dp[3][2]\).
\(\displaystyle (i,x)=(4,7)\to(3,2)\)
3
В ячейке \(dp[3][2]=3\) предмет 3 взять нельзя, потому что \(w_3=4>2\). Следовательно, переходим выше, к \(dp[2][2]\).
dp[3][2]=dp[2][2]=3
4
В ячейке \(dp[2][2]=3\) предмет 2 также нельзя взять: \(w_2=3>2\). Переходим к \(dp[1][2]\).
dp[2][2]=dp[1][2]=3
5
В ячейке \(dp[1][2]=3\) выполняется вариант с предметом 1: \(dp[0][0]+3=3\). Записываем предмет 1 и приходим в начальное состояние.
\(\displaystyle dp[1][2]=dp[0][0]+c_1=0+3=3\)
№
Ответ примера

Обратный ход дал предметы \(4\), затем \(1\). После разворота получаем порядок \(1,4\). Их масса равна \(2+5=7\), стоимость — \(3+7=10\). Если порядок предметов не важен, можно вывести «1 4».

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

Микропроверка

В задаче о рюкзаке при восстановлении из \(dp[i][x]\) оказалось, что \(dp[i][x]=dp[i-1][x]\). Что это означает?

Когда ответ восстанавливается по минимуму или максимуму

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

\[dp[s]=\min_{a\in A(s)}\bigl(cost(a)+dp[next(s,a)]\bigr)\]

Значит, из состояния \(s\) можно выбрать действие \(a\), если выполняется равенство \(dp[s]=cost(a)+dp[next(s,a)]\). Для максимизации знак минимума заменяется на максимум.

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

T
Восстановление пути в графе состояний

Если \(dp[v]\) — оптимальная стоимость достижения вершины \(v\), то ребро \(u\to v\) входит в оптимальный путь, когда \(dp[v]=dp[u]+weight(u,v)\). Идя от конечной вершины к начальной по таким рёбрам, получают оптимальный путь.

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

Массив предков и реализация

Массив предков делает обратный ход проще. Вместо повторной проверки всех переходов программа при улучшении значения записывает \(parent[s]\) — предыдущее состояние, а иногда и \(action[s]\) — выполненное действие.

\[dp[s']\leftarrow dp[s]+cost(s,a),\qquad parent[s']\leftarrow s,\qquad action[s']\leftarrow a\]

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

Псевдокод
cur = finish
answer = []
while cur != start:
    answer.append(action[cur])
    cur = parent[cur]
answer.reverse()
print(answer)
!
Частые ошибки

1. Выводят только значение \(dp\), но не восстанавливают выбранные действия. 2. Идут по таблице в прямом направлении и теряют информацию о предшественнике. 3. Не разворачивают список после обратного хода. 4. При равенстве переходов выбирают недопустимый вариант или забывают требование о лексикографическом порядке. 5. Для рюкзака после выбора предмета не уменьшают вместимость на \(w_i\). 6. Используют ячейку текущего предмета вместо строки \(i-1\), из-за чего предмет можно выбрать несколько раз.

Как оформить решение на экзамене

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

  • Определено, что означает \(dp\).
  • Названо конечное состояние.
  • Для каждого шага указан предыдущий переход.
  • Список действий развернут, если восстановление шло назад.
  • Проверены ограничения и итоговое значение.
Q
Быстрый тест по теме

Быстрая проверка

~ 2 мин4 вопроса
Вопрос 1 / 4
Вопрос 1 из 4 · направление
В каком направлении обычно выполняют восстановление?
Главное за минуту

Главное

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