Динамическое программирование

Сентябрь 12, 2022

Главная
Математика
Динамическое программирование

Содержание

2. Ричард Беллман Ричард Эрнст Беллман (англ. Richard Ernest Bellman; 1920—1984) — американский математик, один из ведущих
3. Последовательность Фибоначчи Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1, Fn = Fn
4. Рекурсия int F(int n) { if (n else return F(n - 1) + F(n - 2);
5. Сохранение промежуточных результатов int F(int n) { if (A[n] != -1) return A[n]; if (n else
6. Самое простое решение F[0] = 1; F[1] = 1; for (i = 2; i F[i] =
7. Одномерное динамическое программирование Задача 1. Посчитать число последовательностей нулей и единиц длины n, в которых не
8. Двумерное динамическое программирование Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в
9. Задача о рюкзаке Имеется набор из N предметов, каждый предмет имеет массу Wi и стоимость Pi,
10. Методы Полный перебор Динамическое программирование Метод ветвей и границ Жадный алгоритм
11. Динамическое программирование Value [W, N] – максимальная сумма, которую надо найти. Суть метода– на каждом шаге
12. Если его взять то вес станет W-Wi , тогда Value[W, i] = Value[W – Wi ,
13. Метод ветвей и границ
16. Скачать презентацию

Слайд 2

Ричард Беллман
Ричард Эрнст Беллман (англ. Richard Ernest Bellman; 1920—1984) — американский математик, один из ведущих

специалистов в области математики и вычислительной техники.

Слайд 3

Последовательность Фибоначчи
Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 при n > 1.
Необходимо найти Fn по

номеру n.

Слайд 4

Рекурсия
int F(int n) {
if (n < 2) return 1;

else return F(n - 1) + F(n - 2);
}

Слайд 5

Сохранение промежуточных результатов
int F(int n) {
if (A[n] != -1)

return A[n];
if (n < 2) return 1;
else {
A[n] = F(n - 1) + F(n - 2);
return A[n];
}
}

Слайд 6

Самое простое решение
F[0] = 1;
F[1] = 1;
for (i =

2; i < n; i++) {
F[i] = F[i - 1] + F[i - 2];
}

Слайд 7

Одномерное динамическое программирование
Задача 1. Посчитать число последовательностей нулей и единиц длины n, в

которых не встречаются две идущие подряд единицы.

Слайд 8

Двумерное динамическое программирование
Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать

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

Слайд 9

Задача о рюкзаке
Имеется набор из N предметов, каждый предмет имеет массу

Wi и стоимость Pi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W – вместимость ранца. Wi , Pi , W – целые неотрицательные числа.

Слайд 10

Методы
Полный перебор
Динамическое программирование
Метод ветвей и границ
Жадный алгоритм

Слайд 11

Динамическое программирование
Value [W, N] – максимальная сумма, которую надо найти.
Суть

метода– на каждом шаге по весу 1

Слайд 12

Если его взять то вес станет W-Wi , тогда Value[W, i]

= Value[W – Wi , i-1] + Pi (для Value[W – Wi , i-1] решение уже найдено остается только прибавить Pi).
Если его не брать то вес останется тем же и Value[W , i] = Value[W , i-1].
Из двух вариантов выбирается тот, который дает наибольший результат.

Слайд 13

Метод ветвей и границ

Слайд 14