Ленивая динамика.

Материал из Algocode wiki
Версия от 16:51, 22 октября 2019; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Ленивая динамика

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

Решим, например, обычную задачу о рюкзаке таким образом. Изначально все $dp[i][j]=-1$, это будет обозначать, что значение еще не посчитано, кроме $dp[0][j]=0$.

 1 int calc(int i, int j) {
 2     if (dp[i][j] == -1) {
 3         dp[i][j] = calc(i - 1, j);
 4         if (a[i] <= j) {
 5             dp[i][j] = max(dp[i][j], calc(i - 1, j - a[i]) + c[I]);
 6         }
 7     }
 8     return dp[i][j];      
 9 }
10 
11 answer = 0
12 for (int j = 0; j <= W; j++) {
13     answer = max(answer, calc(n, j))};
14 }

Время работы так же составит $O(nW)$, так как каждое значение мы считаем только один раз, но истинное время работы будет в несколько раз больше, потому что константа на вызовы функции значительно выше чем на простой цикл.

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



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin