Лабораторија 11 Динамичко програмирање на структури на податоци и алгоритми (серија 1AB)
Кориснички алатки
Алатки за страницата
Странична лента
содржина
1 Лабораториски цели
2 Динамичко програмирање
2.1 Преглед
Динамичното програмирање вклучува решавање на проблем со распаѓање во подпроблеми и нивно решавање. За разлика од divide et impera, подпрограмите не се неповрзани, туку се преклопуваат.
Со цел да се избегне повторна пресметка на преклопуваните делови, решението се прави почнувајќи од најмалите подпрограми и користејќи го нашиот резултат го пресметуваме веднаш поголемиот подпроблем. Најмалите подпроблеми се нарекуваат унитарни подпроблеми, кои можат да се решат во постојана сложеност, на пр. Најголемата низа во множество на еден елемент.
2.2 Имплементација
2.3 Типични проблеми решени со овој алгоритам
2.3.1 Проблем со ранецот
Решението е конструирано со динамично програмирање, D [i] [j] = најдобрата цена добиена за првите i објекти, имајќи ја максималната тежина j.
Релацијата на повторување е како што следува: D [i] [j] = максимум (D [i-1] [j], D [i-1] [jG [i]] + C [i]], каде што G [i] = тежината на објектот i, и C [i] = цената на објектот.
Идејата е следна: На сегашното решение или воопшто не додаваме објект i и остануваме по цена за i-1 објекти или додаваме објект i, во тој случај ги додаваме неговите трошоци на добиената цена за првите i-1 објекти и тежината j-G [i].
2.3.2 Определување на најдолгиот растечки ред
Пример: за низа 24,12,15,8,19 одговорот е низа 12,15,19.
Започнуваме со одредување на секој елемент на должината на најдолгата строго нагорна низа што започнува со првиот елемент и завршува во тој елемент. Оваа вредност ја нарекуваме најдобра и ја применуваме рекурзивната формула најдобро i = 1 + max (најдобар j), со jn, тогаш можеме да го препишеме P (n) = ∏ (Cn, k X k), каде k = 0,1,2, н.
Нека coef (P, k) = коефициент на X k во полиномот П. Потоа можеме да ги напишеме следниве 2 својства:
Може да заклучиме врска помеѓу коефициентите на полиноми од типот P (n) ако запишеме P (n + 1) = (X + 1) P (n) = X P (n) + P (n).
Но, coef (P (n), k) = C (n, k), така што добивме повторување што користи само еден додаток.
Вежби
3. Лабораториски вежби (Linux)
За оваа лабораторија можете да го преземете скелетот на кодот тука. Преземете ја архивата и отпакувајте ја.
Линукс
Можете да ја користите алатката wget за преземање и алатката за отпакување за откопчување.