Clasa a 7-a Lecția 25: Programare dinamică (2)

Înregistrare video lecție

Load video

YouTube

YouTube might collect personal data. Privacy Policy

ContinueDismiss

Problema rucsacului

Atenție: veți avea la temă ca aplicație problema Rucsac1.

Se dă o mulțime formată din N obiecte, fiecare având o greutate și o valoare. Într-un rucsac putem încărca o greutate maxim G. Ne dorim să încărcăm rucsacul cu obiecte astfel încât să maximizăm valoarea totală.

Problema este una foarte practică, ne dorim să optimizăm raportul valoare/greutate, încărcând obiecte cât mai valoroase, dar cât mai ușoare.

Exemplu

Să presupunem că avem următoarele obiecte:

Nr.	1	2	3	4	5	6
Greutate	3	3	1	1	2	1
Valoare	7	4	2	9	4	5

Rucsacul are mărime 10. Care este valoarea maximă a obiectelor ce pot fi încărcate în rucsac?

Singura posibilitate este să alegem obiectele { 1, 2, 4, 5, 6 }. Ele au greutatea totală 10 și valoarea totală 29.

Încercarea 1: după obiecte

Definirea problemei de programare dinamică nu este evidentă. Voi încerca să arăt un mod de gândire posibil, care implică mai multe posibilități pe care le vom verifica și apoi elimina, ajungând în final la o definire bună a problemei.

Să definim

V[i] = valoarea maximă ce se poate obține cu primele i greutăți, astfel încât greutatea totală să nu depășească G

Are V[i] proprietatea de optimalitate a subproblemelor?

Să considerăm o soluție optimă, V[i]. Ea va conține unele din primele i obiecte. Ultimul obiect este obiectul k ≤ i. Atunci este V[k] optimă?

Nu neapărat! Este posibil să găsim o soluție V[k] cu valoare mai mare, dar pe care să nu o putem folosi în construcția problemei V[i] deoarece am depăși greutatea.

Concluzie: nu putem folosi programarea dinamică cu o astfel de definire a problemei.

Încercarea 2: după greutatea totală

Să facem o altă încercare. Să definim

V[g] = valoarea maximă ce se poate obține într-un rucsac de mărime g

Are V[g] proprietatea de optimalitate a subproblemelor?

Să considerăm o soluție optimă, V[g]. Ea va conține unele obiecte, a căror sumă a greutăților nu depășește g. Fie ultimul obiect folosit obiectul k ce are greutate G_k. Este V[g-Gk] optimă?

Răspunsul este: nu, deoarece s-ar putea ca optimul să includă V[g] (pe care nu avem voie să o folosim de două ori).

Concluzie: nu putem folosi programarea dinamică nici cu această definire a problemei.

Încercarea 3: după obiecte și greutate totală

Să încercăm să combinăm cele două încercări de mai sus. Să definim

V[i][g] = valoarea maximă ce se poate obține cu primele i greutăți într-un rucsac de mărime g

Are V[i][g] proprietatea de optimalitate a subproblemelor?

Să considerăm o soluție optimă V[i][g]. Fie ultimul obiect folosit obiectul k ce are greutate G_k. Este V[k][g-Gk] optimă? Să presupunem că nu ar fi. Atunci am putea găsi o valoare mai mare, folosind primele k obiecte ce vor încăpea în greutatea g-G_k. Putem folosi această valoare pentru a obține o valoare mai mare pentru problema originală, V[i][g].

Concluzie: putem folosi programarea dinamică cu această definiție a problemei.

Construim formula de recurență. Pentru a calcula V[i][g] avem două variante:

• Fie nu folosim greutatea G_i, caz în care vom obține valoarea V[i-1][g] (aceeași greutate, dar folosind primele i-1 obiecte).
• Fie folosim greutatea G_i, caz în care vom obține valoarea V[i-1][g-Gi] + Pi (greutatea este cea care rămâne în rucsac după ce folosim G_i, și apoi putem folosi primele i-1 obiecte).

$V[i][g]={\begin{cases}0,&{\text{dacă }}i=0{\text{ sau }}g=0\\max(V[i-1][g],V[i-1][g-G_{i}]+P_{i})&{\text{în caz contrar}}.\end{cases}}$

Unde (G_i, P_i) sunt greutatea, respectiv valoarea obiectului i.

Răspunsul la problemă este elementul V[N][G].

Exemplu

Fie obiectele din exemplul de mai sus:

Nr.	1	2	3	4	5	6
Greutate	3	3	1	1	2	1
Valoare	7	4	2	9	4	5

Vom completa, pe linii, următorul tabel:

Obiect	0	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	7	7	7	7	7	7	7	7
2	0	0	0	7	7	7	11	11	11	11	11
3	0	2	2	7	9	9	11	13	13	13	13
4	0	9	11	11	16	18	18	20	22	22	22
5	0	9	11	13	16	18	20	22	22	24	26
6	0	9	14	16	18	21	23	25	27	27	29

Analiză

Acest algoritm are complexitate O(N·G). Memoria folosită este O(G) dacă memorăm doar o linie din matrice. Dacă dorim să aflăm și o soluție maximală (obiectele din componența soluției), nu doar mărimea ei, vom avea nevoie de memorie O(N·G), precum vom vedea mai jos.

Există un algoritm care reduce necesarul de memorie la O(G).

Reconstrucția soluției

Dorim să aflăm nu doar valoarea maximă, ci și obiectele selectate. Cum procedăm?

Pentru a putea reconstrui soluția vom memora în fiecare căsuță, direcția din care provine ea, adică din care am calculat acel maxim. Direcția poate fi spre stânga-sus sau spre în sus. Apoi vom porni din elementul V[N][G] și vom urma aceste direcții până ce ieșim din matrice. De fiecare dată când urmăm o diagonală reținem obiectul selectat, care este chiar rândul curent. Astfel, descoperirea obiectelor se face în ordine inversă.

Distanța edit (Levenshtein)

Atenție: veți avea această problemă la temă.

Se dau două șiruri de caractere, X și Y. Putem efectua trei operațiuni asupra șirului X:

• Inserare caracter la orice poziție
• Ștergere caracter la orice poziție
• Suprascriere - înlocuire a unui caracter cu un alt caracter

Care este numărul minim de operații asupra șirului X care îl transformă în șirul Y?

Definim distanța edit ca fiind acest număr minim de operații. Deoarece operațiile sunt unele frecvente într-un editor de texte, de aici vine și denumirea de distanță edit.

Exemplu

Acest exemplu este inspirat de la wikipedia.

Fie șirurile:

X: KITTEN
Y: SITTING

Numărul minim de operații pentru a transforma X în Y este 3. De exemplu:

1. Înlocuim K cu S: KITTEN → SITTEN
2. Înlocuim E cu I: SITTEN → SITTIN
3. Adăugăm la final un G: SITTIN → SITTING

Soluție

Problema este aproape identică cu subsecvența maximală comună a două șiruri. Vom defini:

D(i, j) = numărul minim de operații ce transformă șirul X[1..i]] în șirul Y[1..j]

Nu voi face demonstrația optimalității subproblemelor, deoarece este similară cu ce de la subsecvența maximală comună a două șiruri.

Obținem relația de recurență:

$\operatorname {D} _{X,Y}(i,j)={\begin{cases}\max(i,j)&{\text{ dacă }}\min(i,j)=0,\\\min {\begin{cases}\operatorname {D} _{X,Y}(i-1,j)+1\\\operatorname {D} _{X,Y}(i,j-1)+1\\\operatorname {D} _{X,Y}(i-1,j-1)+X_{i}\neq Y_{j}\end{cases}}&{\text{ în caz contrar.}}\end{cases}}$

Distanța edit între cele două șiruri este D(m, n).

Analiză

Acest algoritm are complexitate O(m·n), unde m și n sunt lungimile șirurilor. Memoria folosită este O(min(m, n)) dacă memorăm doar o linie din matrice. Dacă dorim să aflăm și operațiile efectuate, nu doar numărul lor, vom avea nevoie de memorie O(m·n), precum vom vedea mai jos.

Există un algoritm care reduce necesarul de memorie la O(min(m, n)) chiar și cu reconstrucția soluției.

Reconstrucția soluției

Dorim să aflăm nu doar distanța dintre cele două șiruri, ci și o secvență de operații. Cum procedăm? În mod similar cu subsecvența maximală comună.

Pentru a putea reconstrui soluția vom memora în fiecare căsuță din matrice direcția din care provine ea, adică din care am calculat acel maxim. Direcția poate fi spre stânga, spre sus, sau în diagonală stânga-sus. Apoi vom porni din elementul v[]D[m][n]</source> și vom urma aceste direcții până ce ieșim din matrice. Astfel:

• Direcția spre stânga înseamnă o inserare de caracter.
• Direcție spre sus înseamnă o ștergere de caracter.
• Direcția diagonală înseamnă:
  • O suprascriere dacă caracterele respective sunt diferite.
  • Nimic (nici o operație) dacă caracterele sunt egale.

Înmulțirea optimală a unui șir de matrice

Se dă un produs matricial de N matrice. Înmulțirea matricelor este asociativă, deci nu contează în ce ordine efectuăm înmulțirile. Dar numărul de operații elementare va diferi în funcție de ordine. Să se găsească o ordine de înmulțire care minimizează numărul de înmulțiri elementare.

Vom discuta pe scurt această problemă, deoarece matematica necesară depășește nivelul clasei a șaptea.

Cei interesați pot rezolva problema: Pdm ca aplicație.

Numărare optime prin programarea dinamică

Câte soluții distincte posibile admite o problemă de programare dinamică?

Orice problemă de programare dinamică admite un optim. Soluția optimă nu este, de obicei, unică. Putem, deci, pune întrebarea:

Care este numărul de soluții optime ale unei probleme de programare dinamică?

Răspunsul se poate da foarte ușor, folosind același tabel cu care calculăm subproblemele. Vom memora, pe lîngă valoarea maximă (sau minimă) și numărul de moduri în care se poate ajunge la ea.

Exemplu: subsecvența crescătoare de lungime maximă

Să luăm exemplul de data trecută: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

Avem formula de recurență: L[i] = max(L[j]+1), j > i și V[j] ≥ V[i]

Vom calcula și MAX[i] ca fiind suma tuturor MAX[j] pentru acei indecși j unde relația de maxim este satisfăcută.

Exemplu:

V0841221061419513311715L6453534243323221MAX4722232172312111

Avem, deci, patru secvențe crescătoare de lungime maximală, anume 6. Toate încep cu elementul 0. Două dintre ele continuă cu elementul 4, celelalte două cu elementul 2.

Explicație: elementul curent se poate atașa oricărei secvențe maximale anterior găsite. Dacă o secvență anterioară avea k posibilități de formare, atunci și noile secvențe formate vor fi tot în număr de k. Dacă avem mai multe posibilități de secvențe anterioare, toate vor contribui în egală măsură. De aceea le însumăm.

Discuție: problema rucsacului

Discuție despre cum calculăm numărul de soluții posibile în cazul problemei rucsacului: pe baza relației de recurență calculăm numărul de soluții. El se poate "transfera" de la elementul generator. Sau, în caz că ambele moduri de generare duc la același profit vom însuma numărul de soluții.

Probleme suprapuse (numărare soluții neoptimale)

Există unele probleme care nu cer să se determine un optim, ci să se numere soluții. Ele nu se rezolvă prin programare dinamică, deoarece nu se cere optimul. Ele sunt adesea confundate cu probleme de programare dinamică.

În realitate ele sunt probleme de numărare, folosind structura de probleme suprapuse.

Să luăm câteva exemple.

Rucsac

Atenție: veți avea această problemă la temă.

Problema rucsac cere să se calculeze câte subsecvențe distincte (necontigue) au suma egală cu un număr dat.

Problema este echivalentă cu cea a rucsacului: numerele de la intrare reprezintă atât greutatea cât și valoarea obiectelor. Însă trebuie să selectăm obiecte astfel încât suma greutăților să fie exact K, numărul dat.

Exemplu

Fie numerele: 8 3 6 5 2 și numărul dat K = 11.

Vom avea trei subsecvențe distincte a căror sumă este 11:

8 3 3 6 2 6 5

Soluție

Observație importantă:

Nu putem folosi definiția anterioară a problemei, deoarece ea admite soluții care nu "umplu" exact rucsacul. Aceste soluții nu sunt admisibile.

Vom defini problema ușor diferit:

V[i][g] = valoarea maximă ce se poate obține cu primele i greutăți într-un rucsac de mărime g complet umplut. Valoarea va fi zero dacă nu putem umple greutatea g.

În cazul nostru, deoarece valoarea este egală cu greutatea acea valoare va fi chiar greutatea g. Problema se transformă în există un mod de a forma o greutate g cu primele i obiecte? Răspunsul este unu dacă este afirmativ, sau zero dacă nu se poate forma o greutate. Matricea va fi o matrice de zero și unu.

Formula de recurență se modifică și ea, puțin:

\( V[i][g] = \begin{cases} 0, & \mbox{dacă } i = 0 \text{ și } g > 0 \\ 1, & \text{dacă } g = 0 \\ or(V[i-1][g], V[i-1][g-G_{i}]) & \text{în caz contrar}. \end{cases} \)

unde or(x, y) este 1 dacă măcar unul dintre x, y este 1, sau zero în caz contrar.

Pe ultima linie a matricei V vom avea 1 pentru greutățile ce se pot obține.

Acum: cum modificăm soluția să calculeze nu doar dacă o greutate se poate obține, ci în câte moduri distincte?

Vom calcula:

NSOL[i][g] = numărul de moduri în care putem forma greutatea g folosind primele i numere. Acest număr va fi zero dacă greutatea nu se poate obține.

Formula de recurență este aproape identică cu cea anterioară.

\( NSOL[i][g] = \begin{cases} 0, & \text{dacă } i = 0 \mbox{ și } g > 0 \\ 1, & \text{dacă } g = 0 \\ NSOL[i-1][g] + NSOL[i-1][g-G_{i}] & \text{în caz contrar}. \end{cases} \)

Numărul de moduri în care putem alege numere de sumă K este NSOL[N][K], elementul din colțul din dreapta-jos al matricei NSOL.

Exemplu

Pentru exemplul anterior, avem numerele: 8 3 6 5 2

și numărul dat K = 11.

Vom calcula tabelul:

01234567891011010000000000011000000010002100100001001310010010110141001011021025101102113123

Avem, deci, trei moduri de a obține suma 11.

Analiză

Algoritmul are aceeași complexitate în timp și memorie ca și problema originală, anume O(N·K) timp și O(K) memorie, dacă memorăm doar o linie a matricei.

Cifreco

Atenție: veți avea această problemă la temă.

Problema cifreco a fost dată la ONI 2012 baraj gimnaziu. Deși se poate rezolva cu alte metode, ea are o rezolvare foarte eficientă și simplu de implementat folosind numărarea prin probleme suprapuse.

Problema cere ca, dîndu-se două numere x și y, să se găsească cîte numere există între aceste valori cu proprietățile:

Au N cifre, tot atîtea cifre cîte au și numerele x și y.

Suma cifrelor lor este N+8 (la fel ca și x și y).

Soluție

Să ne propunem mai întîi să rezolvăm o problemă mai simplă: cîte numere de N cifre au suma cifrelor N+8? Cu alte cuvinte nu vom ține cont de valorile x și y.

Descompunerea în subprobleme suprapuse nu este foarte evidentă. Vom introduce o dimensiune auxiliară: vom varia suma cifrelor. Astfel, definim:

NSOL[N][S] = numărul de numere de N cifre a căror sumă este S.

Ce formulă de recurență avem?

Cum se poate forma un număr de N cifre? Punînd pe prima poziție toate cifrele permise și apoi formând un număr cu N-1 cifre. Vom avea, deci:

NSOL[N][S] = NSOL[N-1][S-1] + NSOL[N-1][S-2] + ... + NSOL[N-1][N-1]

Astfel:

Primul termen este numărul de numere care încep cu 1

Al doilea termen este numărul de numere care încep cu 2

...

Ultimul termen este numărul de numere care încep cu S - N + 1, aceasta fiind cea mai mare cifră pentru care cifrele rămase mai pot forma suma N-1.

Am putea să pornim la implementare. Însă mai putem face o optimizare. Să observăm că, conform definiției:

NSOL[N][S-1] = NSOL[N-1][S-2] + ... + NSOL[N-1][N-1]

De aici rezultă o formulă mai simplă de calcul pentru NSOL[N][S]:

NSOL[N][S] = NSOL[N-1][S-1] + NSOL[N][S-1]

Vom completa acest tabel pentru valori maxime. Astfel vom putea răspunde în O(1) la întrebări de forma:

Câte numere de N cifre au suma S?

Acum revenim la problema noastră. Trebuie să calculăm câte numere de N cifre au suma N+8 între x și y. Cum o rezolvăm?

Ne propunem să calculăm câte numere sunt mai mici sau egale cu k. Fie, de exemplu, k = 623. Vom proceda astfel:

Vom calcula câte numere încep cu 1 și au suma cifrelor 11. Ele sunt toate mai mici strict ca 623. Vom folosi NSOL[2][10].

Vom calcula câte numere încep cu 2 și au suma cifrelor 11. Vom folosi NSOL[2][9].

...

Vom calcula câte numere încep cu 5 și au suma cifrelor 11. Vom folosi NSOL[2][6].

În acest moment ne-au rămas doar numere care încep cu 6. Câte vor fi ele? Atâtea câte numere există mai mici ca 23, a căror sumă a cifrelor să fie 5. Reluăm, deci, problema de mai sus cu alți parametri, continuând să adunăm.

Putem acum calcula:

NN(k) = numărul de numere mai mici sau egale cu un număr k.

Pentru a răspunde la problemă vom calcula:

NN(x, y) = NN(y) - NN(x) + 1

Ce complexitate are această soluție?

Calculul tabelului este O(N·Σ) - un număr foarte mic, circa 162. Mărimea tabelului va fi aceeași.

Calculul răspunsului necesită o plimbare prin cifre, efectuată pentru fiecare cifră a numărului x sau y. Este, deci O(suma cifrelor) = O(N) - un număr și mai mic, circa 54.

Aveți această problemă la temă.

Atenție! Calculul numărului de numere mai mici sau egale cu k se poate face mai ușor pornind de la cea mai din dreapta cifră, în loc de cea mai din stânga. Ideea este aceeași, doar ordinea de calcul se inversează.

Șir2

Problema șir2 este o problemă tipică de numărare folosind probleme suprapuse. Ne vom ocupa doar de al doilea subpunct care cere să se calculeze în câte feluri se poate scrie un număr N ca sumă de M numere nenule. Ordinea termenilor contează.

Vom avea o recurență similară cu cea de la cifreco:

NSOL[M][S] = numărul de secvențe de numere nenule de lungime M a căror sumă este S.

Recurența nu este foarte grea. Similar cu cifreco avem:

NSOL[M][S] = NSOL[M-1][S-1] + NSOL[M-1][S-2] + ... + NSOL[M-1][M-1]

Astfel:

Primul termen este numărul de secvențe care încep cu 1.

Al doilea termen este numărul de secvențe care încep cu 2.

...

Ultimul termen este numărul de secvențe care încep cu S-M+1, aceasta fiind cel mai mare număr pentru care cifrele rămase mai pot forma suma M.

La fel ca la cifreco, putem reduce această recurență la una mai simplă:

NSOL[M][S] = NSOL[M-1][S-1] + NSOL[M][S-1]

Soluția problemei va fi elementul NSOL[M][N].

Observații:

Aveți grijă la calcule, ele trebuie făcute modulo 104729.

Din toate elementele unei sume putem scădea 1. Obținem un șir de elemente naturale, posibil nule, a căror sumă echivalentă trebuie micșorată cu M.

Astfel, problema se simplifică dacă:

Considerați că numerele pot fi nule

Reduceți suma cerută, N, înlocuind-o cu N-M.

Numărul de posibilități rămâne același, dar tabelul se simplifică.

Ce complexitate are acest algoritm?

El este O(M·(N-M)) ca timp și memorie.

Tema 26 - cercul de informatică pentru performanță clasa a șaptea

Tema 26 presupune să se rezolve următoarele probleme (program C trimis la NerdArena):

rucsac1 ca aplicație la problema rucsacului.

șiruri2 ca aplicație la distanța edit.

rucsac ca aplicație de numărare cu probleme suprapuse

cifreco dată la ONI 2012 baraj gimnaziu, ca aplicație de numărare cu probleme suprapuse

Tema opțională

Tema 26 opțională presupune să rezolvați următoarele probleme (program C trimis la NerdArena):

pdm ca aplicație la înmulțirea optimală de matrice

cutii problemă simpatică