Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-11 [2017/02/15 22:27] sebastian.cancel |
laboratoare:laborator-11 [2017/05/09 13:50] mihai.iacov [Exerciții] |
||
---|---|---|---|
Linia 29: | Linia 29: | ||
====2.3 Probleme tip rezolvate cu acest algoritm==== | ====2.3 Probleme tip rezolvate cu acest algoritm==== | ||
===2.3.1 Problema rucsacului=== | ===2.3.1 Problema rucsacului=== | ||
+ | Soluția se construiește prin programare dinamică, D[i][j]=cel mai bun cost obținut pentru primele i obiecte, având greutatea maxim j.\\ | ||
+ | Relația de recurență este următoarea: | ||
+ | Ideea este următoarea: | ||
+ | |||
+ | ===2.3.2 Determinarea celui mai lung subșir crescător=== | ||
+ | Exemplu: pentru șirul 24, | ||
+ | Începem prin a stabili pentru fiecare element lungimea celui mai lung subșir strict crescător care începe cu primul element și se termină în elementul respectiv. Numim această valoare //best// și aplicăm formula recursivă //best i=//1 + max(//best j//),cu //j < i// și //elem j < elem i// | ||
+ | Aplicând acest algoritm obținem: elem 24, | ||
+ | \\ | ||
+ | \\ | ||
+ | Pentru 24 sau 12 nu există nici un alt element în stânga lor strict mai mici decât ele, de aceea au best egal cu 1.\\ | ||
+ | Pentru elementele 15 se poate găsi în stânga lor 12 strict mai mic decât ele. Pentru 19 se găsește elementul 15 strict mai mic decât el. Cum 15 deja este capăt pentru un subșir soluție de 2 elemente, putem spune că 19 este capătul pentru un subșir soluție de 3 elemente.\\ | ||
+ | \\ | ||
+ | Pentru a găsi care sunt elementele ce alcătuiesc subșirul strict crescător putem să reținem și o 'cale de întoarcere' | ||
+ | Reconstrucția astfel obținută are complexitatea O(N). | ||
+ | \\ | ||
+ | Exemplu: Subproblema care se termină în elementul 19 are subșirul de lungime maximă 3 și a fost calculată folosind subproblema care se termină cu elementul 15 (oricare din ele). Subșirul de lungime maximă care se termină în 15 a fost calculat folosindu-ne de elementul 12. 12 marchează sfârșitul reconstrucției, | ||
+ | \\ | ||
+ | |||
+ | ===2.3.3 Combinări de n luate câte k === | ||
+ | |||
+ | ==== Exerciții ==== | ||
+ | |||
+ | - Construiți o funcție care calculează f(n), unde f = șirul lui Fibonacci; | ||
+ | - Construiți o funcție care calculează f(n, k), unde f = combinări de n luate câte k; | ||
+ | - implementați problema rucsacului; | ||
+ | - Construiți o funcție care indică ordinea operațiilor la înmulțirea a N matrici pentru a minimiza numărul de înmulțiri între 2 numere; | ||
+ | - construiți o funcție care calculează f(n) = 5< | ||
+ | - Se dă un vector cu N elemente (v = [v1 v2 ... vn]) ce poate fi secționat în piese după următoarele reguli: a) inițial, tot vectorul reprezintă o piesă; b) o piesă poate reprezenta doar o bucată continuă (nu sare peste vreun element) din vectorul inițial; c) secționarea unei piese duce la înlocuirea piesei respective cu 2 piese mai mici, fără a se pierde niciun element din vector; d) valoarea unei piese este val = (lungimea piesei) x (suma elementelor din piesă). Găsiți secțiunile ce maximizează suma valorilor pieselor. |