АиФП 5. Динамическое программирование

Июль 26, 2022

Главная
Информатика
АиФП 5. Динамическое программирование

Содержание

2. Динамическое программирование – метод проектирования алгоритмов. Предложен американским математиком Ричардом Беллманом как общий метод оптимизации многостадийных
3. Иллюстрация метода на примере чисел Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13… F(n)=F(n-1) +
4. 5.1. Вычисление биномиальных коэффициентов Биномиальным коэффициентом С(n, k) называется количество комбинаций (подмножеств) из k элементов из
5. Таблица для вычислений биномиальных коэффициентов
6. Алгоритм Binomial (n,k) // Вх. данные: Пара неотрицательных чисел n≥k ≥0 // Вsх. данные: Значение C(n,k)
7. Оценка эффективности алгоритма вычисления биномиальных коэффициентов Базовая операция – сложение. A(n,k) – общее количество сложений при
8. 5.2. Задача о рюкзаке и функции с запоминанием Дано: Рюкзак вместимостью W Количество предметов: n Веса
9. Экземпляр задачи, определяемый первыми i предметами (1≤i ≤ n) Веса: w1 , w2 , …,wn Стоимости:
10. Все подмножества первых i предметов, которые помещаются в рюкзак ёмкостью j делятся на две категории: те,
11. Рекуррентное соотношение max{V[i-1,j], vi +V[i-1, j-wi]}, если j-wi≥0 V[i,j]= V[i-1,j], если j-wi Начальные условия: V[0,j]=0 при
12. Таблица для решения задачи о рюкзаке методом динамического программирования
13. Пример 1. W=5
14. Ёмкость j
16. Скачать презентацию

Слайд 2

Динамическое программирование – метод проектирования алгоритмов.
Предложен американским математиком Ричардом Беллманом

как общий метод оптимизации многостадийных процессов принятия решений.
Динамическое программирование – метод решения задач с перекрещивающимися подзадачами.

Слайд 3

Иллюстрация метода на примере чисел Фибоначчи
0, 1, 1, 2, 3, 5,

8, 13…
F(n)=F(n-1) + F(n-2), n≥2 (1)
Начальные условия:
F(0)=0, F(1)=1 (2)

Слайд 4

5.1. Вычисление биномиальных коэффициентов
Биномиальным коэффициентом С(n, k) называется количество комбинаций (подмножеств)

из k элементов из n-элементного множества (0≤k≤n).
Название «биномиальные коэффициенты» происходит от участия этих чисел в формуле бинома:
(a+b)n =C(n,0)an +…+ C(n,k)an-kbk +…+C(n,n)bn
C(n,k)= C(n-1,k-1)+ C(n-1,k) при n>k>0 (3)
C(n,0)=C(n,n)=1 (4)

Слайд 5

Таблица для вычислений биномиальных коэффициентов

Слайд 6

Алгоритм Binomial (n,k)
// Вх. данные: Пара неотрицательных чисел n≥k ≥0
// Вsх.

данные: Значение C(n,k)
for i←0 to n do
for j ←0 to min(i,k) do
if j=0 or j=I
C[i,j] ←1
else
C[i,j] ← C[i-1,j-1] + C[i-1,j]
return C(n,k)

Слайд 7

Оценка эффективности алгоритма вычисления биномиальных коэффициентов
Базовая операция – сложение.
A(n,k) – общее

количество сложений при вычислении C(n,k).
k i-1 n k k n
A(n,k)=Σ Σ1 +Σ Σ=1= Σ(i-1)+ Σ k=
i-1 j=1 i=k+1 j=1 i=1 i=k+1
=[(k-1)k]/2+k(n-k)∈O(n×k)

Слайд 8

5.2. Задача о рюкзаке и функции с запоминанием
Дано: Рюкзак вместимостью W

Количество предметов: n
Веса предметов: w1 , w2 , …,wn
Стоимости предметов: v1 , v2 , …,vn
Требуется найти: наиболее ценное подмножество, помещающееся в рюкзаке.

Слайд 9

Экземпляр задачи, определяемый первыми i предметами (1≤i ≤ n)
Веса: w1 ,

w2 , …,wn
Стоимости: v1 , v2 , …,vn
Ёмкость рюкзака: 1≤j ≤ W.
V[i,j] – значение оптимального решения этого экземпляра задачи, т.е. стоимость наиболее ценного подмножества предметов из первых i предметов, которые помещаются в рюкзак ёмкости j.

Слайд 10

Все подмножества первых i предметов, которые помещаются в рюкзак ёмкостью j

делятся на две категории:
те, которые не включают i-й предмет;
те, которые его включают.
Замечания.
Среди подмножеств (ПМ), которые не включают i-й предмет, стоимость оптимального ПМ – V[i-1,j].
Среди ПМ, которые включают i-й предмет, оптимальное ПМ составляется из оптимального ПМ из этого предмета и первых (i-1) предметов, которые размещаются в рюкзаке ёмкостью (j-wi). Стоимость такого оптимального ПМ равна vi+V[i-1,j-wi].

Слайд 11

Рекуррентное соотношение
max{V[i-1,j], vi +V[i-1, j-wi]}, если j-wi≥0
V[i,j]=
V[i-1,j], если j-wi<0

Начальные условия: V[0,j]=0 при j≥0
V[i,0]=0 при i≥0
Цель: Найти V[n,W], т.е. максимальную стоимость подмножества из n предметов, которое помещается в рюкзак ёмкостью W, и само это подмножество.

Слайд 12