ЕГЭОГЭЕНТ
РУҚА
Тапсырмалар № 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 позволяют восстанавливать путь сразу и не проверять формулы повторно.