Динамическое программирование - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Динамическое программирование, слайд №10

Динамическое программирование, слайд №11

Динамическое программирование, слайд №12

Динамическое программирование, слайд №13

Динамическое программирование, слайд №14

Динамическое программирование, слайд №15

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Динамическое программирование. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

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