Презентация на тему АиФП 5. Динамическое программирование

математиком Ричардом Беллманом как общий метод оптимизации многостадийных процессов

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

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

F(1)=1 (2)

количество комбинаций (подмножеств) из 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)

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)

сложение.
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)

Рюкзак вместимостью W
Количество предметов: n
Веса предметов: w1

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

n)
Веса: w1 , w2 , …,wn
Стоимости: v1 ,

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

рюкзак ёмкостью j делятся на две категории:
те, которые не

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

если j-wi≥0
V[i,j]=
V[i-1,j], если j-wi

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

программирования

Ёмкость j