8vfgd ger df fsdgv cv PDF

Preview

Summary

wsdswdh grgterg vdv efreg wqeqeere bfdb...

Description

Outline Cuprins 1 Paradigme de proiectare a algoritmilor

1

2 Probleme de optimizare

1

3 Paradigma greedy

2

4 Exemple de probleme care pot fi rezolvate prin strategii greedy 2 4.1 Bin-packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4.2 Plata unei sume folosind num˘ar minim de bancnote . . . . . . . . 3 3 4.3 Problema select, iei activit˘at, ilor . . . . . . . . . . . . . . . . . . . 4.4 Algoritmii greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.5 Problema rucsacului - varianta continu˘a . . . . . . . . . . . . . . 8 4.6 Problema codurilor Huffman . . . . . . . . . . . . . . . . . . . . 9 4.7 Matroizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.8 Problema APM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1

Paradigme de proiectare a algoritmilor

Conform DEX, . O paradigm˘a de proiectare a algoritmilor este o metod˘a general˘a de a rezolva o clas˘a de probleme. Dintre cele mai importante paradigme de proiectare a algoritmilor fac parte divide et impera (vezi cursul Structuri de Date), greedy (acest curs), programare dinamic˘a (cursurile urm˘atoare) s, i backtracking.

2

Probleme de optimizare

Paradigma greedy este folosit˘a ˆın special pentru a rezolva probleme de optimizare, adic˘a probleme ˆın care datele de intrare au orice form˘a, iar datele de ies, ire presupun maximizarea sau minimizarea unei anumite cantit˘at, i, respectˆand anumite constrˆangeri: Problem˘a de optimizare: Input: . . . Output: cel mai mare/cel mai mic num˘ar cu proprietatea c˘a . . . Un exemplu de problem˘a de optimizare este g˘asirea celui mai scurt drum ˆıntre dou˘a noduri ˆıntr-un graf: Problema celui mai scurt drum ˆıntr-un graf: Input: Un graf G = (V, E) s, i dou˘a noduri s, t ∈ V . Output: Lungimea n a celui mai scurt drum de la s la t ˆın graf. ˆIntr-o problem˘a de optimizare, este posibil ca datele de ies, ire s˘a cont, in˘a informat, ii suplimentare. De exemplu, pentru problema celui mai scurt drum ˆıntr-un graf, putem cere s, i drumul de lungime minim˘a (nu doar lungimea acestuia:

1

Problema celui mai scurt drum ˆıntr-un graf (cu output explicit): Input: Un graf G = (V, E) s, i dou˘a noduri s, t ∈ V . Output: v1 , . . . , vn - cel mai scurt drum ˆıntre s s, i t. ˆIn contextul acestei probleme, orice drum ˆıntre s s, i t se numes, te solut, ie, iar un drum ˆıntre s s, i t mai scurt decˆat toate celelalte drumuri ˆıntre s s, i t este solut, ia optim˘ a. ˆIn general, o problem˘a de optimizare cere s˘a alegem din mult, imea de solut, ii posibile (ˆın exemplul de mai sus, mult, imea de drumuri ˆıntre s s, i t), solut, ia optim˘a (cea de cost minim, sau cea de cˆas, tig maxim – ˆın funct, ie de cerint, a problemei). O problem˘a de optimizare este rezolvat˘a corect de un algoritm dac˘a aceasta produce ˆın toate cazurile o solut, ie optim˘a. Exercit¸iul 1. Dat, i alte exemple de probleme de optimizare pe care le-at, i ˆıntˆalnit pˆan˘a acum.

3

Paradigma greedy

Greedy este una dintre cele mai simple paradigme de programare. Multe probleme de optimizare pot fi rezolvate eficient folosind algoritmi greedy. Algoritmii greedy sunt de obicei foarte simplu de implementat, dar nu neap˘arat simplu de demonstrat. Pentru alte probleme de optimizare, algoritmii greedy nu produc solut, ia optim˘a. ˆIn aceste cazuri, exist˘a dou˘a strategii: 1. Dac˘a se dores, te o solut, ie optim˘a, se caut˘a o alt˘a metod˘a de rezolvare decˆat greedy (folosind, e.g., backtracking sau programare dinamic˘a); 2. Dac˘a diferent, a dintre costul optim s, i costul produs de algoritmul greedy este tolerabil˘a ˆın practic˘a, se poate folosi algoritmul greedy (algoritmul a, ˆın acest caz se numes, te algoritm de aproxproduce o solut, ie aproximativ˘ imare).

4

Exemple de probleme care pot fi rezolvate prin strategii greedy

Algoritmii de tip greedy (lacom) sunt aplicat, i deseori ˆın practic˘a, inclusiv ˆın viat, a de zi cu zi. De exemplu, dac˘a plecat, i ˆıntr-o excursie s, i v˘a preg˘atit, i bagajul, vet, i introduce ˆıntˆai ˆın bagaj lucrurile mari s, i apoi cele mici. Aceast˘a strategie v˘a ajut˘a s˘a folosit, i spat, iul din bagaj ˆın mod eficient.

4.1

Bin-packing

Problemele computat, ionale ˆın care la intrare se dau un container ,si o mult, ime de obiecte s, i la ies, ire se cere o modalitate de a aranja obiectele ˆın container se numesc probleme de tip bin-packing s, i apar ˆın diferite domenii. De exemplu, ˆın contextul jocurilor 2D, mai multe sprite -uri (imagini mici (e.g. 128x128 sau 64x64) sau serii de imagini mici reprezentˆand un personaj sau un alt element grafic din joc) trebuie as, ezate f˘ar˘a s˘a se suprapun˘a ˆıntr-un

2

num˘ar cˆat mai mic de imagini de dimensiuni mai mari (e.g. 1024x1024) care pot fi ˆınc˘arcate de placa video ca texturi s, i apoi afis, ate pe ecran cˆat mai eficient. Folosirea unui num˘ar cˆat mai mic de texturi cres, te performant, a jocului s, i din acest motiv este de dorit s˘a “ˆınghesuim” cˆat mai multe sprite-uri ˆıntr-o singur˘a textur˘a. Cele mai multe framework-uri pentru programarea jocurilor cont, in implementarea unor algoritmi pentru sprite-packing (c˘autat, i “sprite packer” folosind un motor de c˘autare). ˆ In cele mai multe cazuri, pentru problemele de tip bin-packing nu se cunoas, te o rezolvare polinomial˘a s, i din acest motiv se prefer˘a un algoritm greedy care calculeaz˘a o solut, ie aproximativ˘a.

4.2

Plata unei sume folosind num˘ ar minim de bancnote

Un alt exemplu de problem˘a unde aplic˘am un algoritm greedy este plata unei sume de bani folosind un num˘ar minim de bancnote. De exemplu, pentru a pl˘ati (exact) 86 de lei, folosim 6 bancnote: una de 50 de lei, trei de 10 lei, una de 5 lei s, i una de 1 leu. Orice alt˘a metod˘a de a pl˘ati suma de 86 de lei foloses, te mai multe bancnote. Formal, problema poate fi exprimat˘a astfel: Problema pl˘at, ii cu num˘ar minim de bancnote. Input: un num˘ar natural n – suma ce trebuie pl˘atit˘a Output: numerele n500 , n200 , n100 , n50 , n10 , n5 , n1 (ni - cˆate bancnote de i RON folosesc), astfel ˆıncˆat Σi∈{500,200,100,50,10,5,1} ni s˘a fie minim˘a s, i n = Σi∈{500,200,100,50,10,5,1} i × ni . Strategia greedy pe care o folosim este s˘a pl˘atim mereu cea mai mare bancnot˘a care este mai mic˘a decˆat suma pe care o avem de achitat. De exemplu, pentru 86 de lei, cea mai mare bancnot˘a este de 50 de lei. R˘amˆan de achitat 36 de lei. Cea mai mare bancnot˘a este de 10 lei. R˘amˆan de achitat 26 de lei. (...). Se poate demonstra c˘a aceast˘a strategie conduce la un num˘ar minim de bancnote, pentru sistemul de bancnote pe care ˆıl avem ˆın t, ar˘a (bancnote de 500, 200, 100, 50, 10, 5, 1). Pentru alte sisteme de bancnote, strategia greedy nu conduce tot timpul la o solut, ie optim˘a. Exercit¸iul 2. Imaginat, i-v˘a c˘a tr˘ait, i ˆıntr-o t, ar˘a ˆın care sunt disponibile bancnote de 1 leu, de 7 lei s, i de 8 lei. Dat, i exemplu de o sum˘a de bani pentru care strategia greedy descris˘a mai sus nu produce solut, ia optim˘a.

4.3

at, ilor Problema select, iei activit˘

Azi, un student poate participa la una sau mai multe activit˘at, i. De exemplu: curs de la 10 la 12 poate participa la cursul PA; codecamp de la 9 la 17 poate participa la CodeCamp; teatru de la 18 la 20 poate merge la teatru; film de la 21 la 22 poate merge la film; club de la 19 la 24 poate merge ˆın club.

3

Scopul studentului este s˘a participe la cˆ at mai multe activit˘ at, i (dar trebuie s˘a participe la fiecare de la ˆınceput la sfˆars, it s, i nu poate fi ˆın dou˘a locuri ˆın ˆ exemplul de mai sus, studentul acelas, i timp). Ce activit˘at, i trebuie s˘a aleag˘a? In poate participa la maxim 3 activit˘at, i: curs, teatru, film sau codecamp, teatru, film. Formal, problema select, iei activit˘at, ilor este urm˘atoarea: Input: n - num˘arul de activit˘at, i s[0..n − 1] - un tablou care cont, ine timpul de ˆınceput al activit˘at, ilor f [0..n − 1] - un tablou care cont, ine timpul de final al fiec˘arei activit˘a,ti a.ˆı. s[i] < f [i] pentru orice 0 ≤ i ≤ n − 1 s, i f este ˆın ordine cresc˘atoare. Output: A ⊆ {0, . . . , n − 1} A este o mult, ime de activit˘at, i care nu se suprapun A este de cardinal maxim. Consider˘am c˘a activitatea i ˆıncepe exact ˆın momentul si s, i se termin˘a put, in ˆınainte de momentul fi . Cu alte cuvinte, activitatea i dureaz˘a de la si (inclusiv) pˆan˘a la fi (exclusiv). Astfel, dou˘a activit˘at, i i, j se suprapun dac˘a [si , fi ) ∩ [sj , fj ) 6= ∅ (remarcat, i faptul c˘a intervalele sunt ˆınchise la stˆanga s, i deschise la dreapta). Exercit¸iul 3. Ar˘atat, i c˘a dou˘a activit˘at, i i, j nu se suprapun (sunt compatibile ˆıntre ele) dac˘a s, i numai dac˘a si ≥ tj sau sj ≥ ti . De exemplu, pentru n = 5 s, i pentru tablourile s s, i f date mai jos: i 0 1 2 3 4 s[i] 10 9 18 21 19 f [i] 12 17 20 22 24, un r˘aspuns corect este: A = {0, 2, 4}. IDEE 1. O prim˘a idee de rezolvare a problemei printr-o strategie greedy este s˘a aleg activit˘at, ile ˆın ordinea duratei lor. De exemplu, ˆın exemplul de mai sus, aleg activitatea 4 deoarece dureaz˘a 1 or˘a, apoi activitatea 1 ,si activitatea 3, deoarece dureaz˘a amˆandou˘a 2 ore. Totus, i, aceast˘a strategie nu conduce ˆın general la o solut, ie optim˘a. De exemplu, pentru urm˘atoarele activit˘at, i: i 0 1 2 s[i] 9 15 17 f [i] 16 18 23, strategia descris˘a mai sus alege activitatea 1, care are durat˘a de 3 ore. Dar activitatea 1 se suprapune atˆat cu 0 cˆat s, i cu 2 s, i deci nu mai putem alege nicio alt˘a activitate. Solut, ia {1} nu este optim˘a, deoarece solut, ia {0, 2} cont, ine mai multe activit˘at, i. IDEE 2. ˆIn continuare, vom vedea o strategie greedy pentru problema select, iei activit˘at, ilor care conduce ˆın toate cazurile la solut, ia optim˘a. Strategia pe care o vom folosi: 1. ˆıncepem cu mult, imea A = ∅; 4

a 2. dintre activit˘at, ile care au r˘amas, alegem activitatea i care se termin˘ cel mai devreme (intuitiv, deoarece ˆımi las˘a timp mai mult pentru urm˘atoarele activit˘at, i); 3. ad˘aug˘am i la A; 4. s, tergem i s, i toate celelalte activit˘at, i care se suprapun cu i din lista de activit˘at, i disponibile; 5. repet˘am procesul dac˘a mai sunt activit˘at, i disponibile. ˆIn pseudocod, strategia de mai sus poate fi descris˘a astfel: • A=∅

(mult, imea de activit˘at, i selectate)

• time = 0 • for i = 0 to n − 1 timpului de final)

(timpul ˆıncepˆand cu care sunt disponibil) (activit˘at, ile sunt deja ˆın ordine descresc˘atoare a

– if s[i] >= time

(sunt disponibil pentru activitatea i)

∗ A = A ∪ {i} (selectez activitatea i) ∗ time = f [i] (marchez c˘a nu pot accepta activit˘at, i mai devreme de f [i]) ˆ Intrebare. Strategia de rezolvare IDEE 1 nu produce tot timpul solut, ia optim˘a. Cum pot fi sigur ca strategia descris˘a ˆın IDEE 2 produce tot timpul aspuns. Putem demonstra acest lucru. solut, ia optim˘a? R˘ ˆIn primul rˆand, vom ar˘ata c˘a, pentru orice mult, ime S de activit˘at, i, exist˘a o submult, ime S ′ de activit˘at, i care: • cont, ine doar activit˘at, i compatibile ˆıntre ele (care nu se suprapun), • este de cardinal maxim s, i • cont, ine activitatea care se termin˘a cel mai devreme din S . Cu alte cuvinte, f˘ar˘a a pierde din generalitate, ˆıntr-o mult, ime de cardinal maxim de activit˘at, i compatibile ˆıntre ele se poate alege activitatea care se termin˘a cel mai devreme: Lem˘ a 1 (Lema de alegere lacom˘a). Fie S ⊆ {0, 1, . . . , n − 1} o mult, ime nevid˘ a arat compatibile ˆıntre ele). de activit˘ at, i (nu neap˘ Fie x activitatea din S care se termin˘ a cel mai devreme. Exist˘ a o submult, ime S ′ ⊆ S a mult, imii S care: • cont, ine doar activit˘ at, i compatibile ˆıntre ele; • este de cardinal maxim (dintre toate submult, imile lui S de activit˘ a,ti compatibile ˆıntre ele); • cont, ine activitatea x: x ∈ S ′ .

5

Proof. Fie S ′′ o submult, ime oarecare a lui S de activit˘at, i compatibile ˆıntre ele de cardinal maxim. Nu s, tim dac˘a x ∈ S ′′ . Fie y activitatea din S ′′ care se termina cel mai devreme. Alegem S ′ = (S ′′ \ {y}) ∪ {x}. Observ˘am c˘a: • S ′ are acelas, i cardinal cu S ′′ ; • S ′ cont, ine x. Mai avem de ar˘atat c˘a S ′′ cont, ine doar activit˘at, i compatibile ˆıntre ele. Cum y este activitatea care se termin˘a cel mai devreme din S ′ s, i cum S ′ cont, ine doar activit˘at, i compatibile ˆıntre ele, rezult˘a c˘a ∀z ∈ S ′ \ {y}, t[y] ≤ s[z]. Dar y ∈ S ′ , S ′ ⊆ S s, i x ∈ S este activitatea din S care se termin˘a cel mai devreme. Deci x se termin˘a ˆınaintea lui y: t[x] ≤ t[y]. Rezult˘a c˘a ∀z ∈ S ′ \ {y}, t[x] ≤ s[z], ceea ce ˆınseamn˘a c˘a x este compatibil˘a cu toate activit˘at, ile din S ′ \ {y}, deci S ′ cont, ine doar activit˘at, i compatibile ˆıntre ele. Am ar˘atat c˘a, f˘ar˘a a pierde optimalitatea, putem alege activitatea care se termin˘a cel mai devreme. Pentru a ar˘ata c˘a algoritmul, ˆın ˆıntregimea sa, produce o solut, ie optim˘a, a mai r˘amas de ar˘atat urm˘atorul aspect: combinarea activit˘at, ii care se termin˘a cel mai devreme cu restul activit˘at, ilor alese de algoritm este o solut, ie optim˘a. Pentru a formaliza acest lucru, avem nevoie de not, iunea de subproblem˘a: Definit¸ie 1. Not˘ am cu St = {i ∈ S | s[i] ≥ t} submult, imea de activit˘ at, i care ˆıncep dup˘ a momentul t. Vom spune c˘a mult, imile St sunt subproblemele problemei init, iale. Subproblema S0 coincide cu problema init, ial˘a. Putem ˆınt, elege strategia greedy prezentat˘a mai sus ca rezolvˆand, rˆand pe rˆand, mai multe subprobleme de forma St . Cu ajutorul lemei de mai sus, putem demonstra proprietatea de substructur˘a optim˘a: Lem˘ a 2 (Proprietatea de substructur˘a optim˘a). Fie St o subproblem˘ a s, i x ∈ St activitatea aleas˘ a prin strategia greedy (cea care se termin˘ a cel mai devreme). Fie A ⊆ St o submult, ime de activit˘ at, i compabilite ˆıntre ele de cardinal maxim a mult, ime A exist˘ a). care cont, ine x (x ∈ A – prin Lema de alegere greedy, aceast˘ Fie B = A \ {x}. Atunci B este o solut, ie optim˘ a pentru Sf [x] . Proof. Presupunem c˘a exist˘a o solut, ie C mai bun˘a decˆat B pentru subproblema Sf [x] . Atunci C ∪ {x} ar fi o solut, ie pentru St mai bun˘a decˆat A, ceea ce contrazice optimalitatea lui A. Demonstrat, ia propriet˘at, ii de substructur˘a optim˘a este ˆın general foarte simpl˘a. Proprietatea de substructur˘a optim˘a ne spune c˘a subsolut, iile unei solut, ii optime sunt la rˆandul lor solut, ii optime pentru subprobleme. Prin induct, ie, folosindu-ne de cele dou˘a leme de mai sus, este us, or de demonstrat corectitudinea algoritmului: a. Teorem˘ a 1. Strategia greedy de mai sus produce o solut, ie optim˘ 6

Proof. Vom proceda prin induct, ie dup˘a mult, imea S de activit˘at, i disponibile. Prin lema de alegere greedy, exist˘a o solut, ie optim˘a A pentru S astfel ˆıncˆat x ∈ A. Prin ipoteza de induct, ie, algoritmul g˘ases, te o solut, ie optim˘a B pentru subproblema T = {i ∈ S | s[i] ≥ f [x]} (T este strict inclus˘a ˆın S). Prin lema de substructur˘a optim˘a, {x} ∪ A este o solut, ie optim˘a (cea g˘asit˘a de algoritm). O demonstrat, ie alternativ˘a, care poate fi mai simplu de ˆınt, eles fiindc˘a pasul inductiv este explicitat: Proof. Fie s1 , . . . , sk lista de activit˘at, i selectat˘a de algoritmul greedy. Presupunˆand c˘a nu e optim˘a, c˘aut˘am cel mai mic num˘ar j ∈ {1, 2, 3, . . .} astfel ˆıncˆat s˘a existe o list˘a optim˘a de activit˘at, i care cont, ine primele j − 1 activit˘at, i din s1 , . . . , sn s, i apoi alte activit˘at, i: s1 , . . . , sj−1 , tj , . . . , tm .(tj 6= sj ) Presupunem c˘a activit˘at, ile din solut, ia optim˘a s1 , . . . , sj−1 , tj , . . . , tm sunt ordonate cresc˘ator (fiind compatibile ˆıntre ele, nu conteaz˘a dac˘a dup˘a timpul de ˆınceput sau dup˘a cel de sfˆars, it – obt, inem aceeas, i ordine). Prin definit, ie, sj este compatibil˘a cu s1 , . . . , sj−1 s, i ˆıncepe mai devreme decˆat tj . Deci s1 , . . . , sj−1 , sj , tj+1 , . . . , tm ar fi s, i ea o solut, ie optim˘a, contrazicˆand minimalitatea lui j . Exercit¸iul 4. Ce se ˆıntˆampl˘a dac˘a problema nu garanteaz˘a c˘a vectorul f este ˆın ordine cresc˘atoare? Ar˘atat, i c˘a cele dou˘a probleme (ˆın care f este ordonat s, i respectiv ˆın care f nu este neap˘arat ordonat) se reduc una la cealalt˘a.

4.4

Algoritmii greedy

Algoritmii greedy 1. Algoritmii greedy = secvent, ˘a de alegeri locale, alegeri care par a fi cele mai bune ˆın momentul respectiv; 2. Odat˘a f˘acut˘a o alegere, nu ne putem r˘azgˆandi. 3. Cˆateodat˘a aceast˘a solut, ie conduce la un optim global (e.g. problema select, iei activit˘a,tilor); alteori nu (e.g. problema discret˘a a rucsacului). Algoritmii greedy - proces de proiectare 1. Identific˘am subprobleme ale problemei de optimizare (e.g. Stime = {i | s[i] ≥ time} astfel ˆıncˆat o alegere greedy ˆıntr-o subproblem˘a s˘a conduc˘a la o alt˘a subproblem˘a). 2. (greedy-choice property) Ar˘at˘am c˘a exist˘a o solut, ie optim˘a a problemei init, iale care foloses, te alegerea greedy. 3. (optimal substructure property) Ar˘at˘am c˘a dac˘a facem o alegere greedy, combinat, ia dintre alegerea greedy s, i o solut, ie optim˘a pentru subproblema rezultat˘a este o solut, ie optim˘a pentru problema init, ial˘a. 7

4.5

Problema rucsacului - varianta continu˘ a

Problema rucsacului - varianta continu˘ a Un hot, a spart un magazin ,si a g˘asit n bunuri. Al i-lea bun valoreaz˘a vi lei ant˘ares, te wi kilograme. Hot, ul are un rucsac care poate s˘a duc˘a cel mult W ,si cˆ kilograme de bunuri. Orice bun poate fi sect, ionat iar valoarea unei p˘art , i este proport, ional˘a cu dimensiunea acesteia (e.g. jum˘atate dintr-un obiect cu vi = 10 ant˘ares, te 3 kg s, i valoreaz˘a 5 lei). Hot, ul vrea s˘a maximizeze valorea ,si wi = 6 cˆ obiectelor pe care le va pune ˆın rucsac. Problema rucsacului - formalizare varianta continu˘ a Input: n, v[0..n − 1], w[0..n − 1], W , toate numere naturale Output: p[0..n − 1], p[i] ∈ [0, 1] astfel ˆıncˆat: 1. Σi p[i]w[i] ≤ W

(p˘art, ile alese ale obiectele ˆıncap ˆın rucsac) (valoarea p˘art, ilor este maxim˘a)

2. Σi p[i]v[i] este maxim a Problema rucsacului - exemplu instant, ˘ Avem n = 3 obiecte: i w[i] v[i]

0 1 2 1 2 3 10 15 20

Rucsacul are capacitate de W = 5 kg. O solut, ie optim˘a pentru varianta continu˘a: 1. iau 100% din primul obiect (deci p[0] = 1). Cˆas, tig: 1×10 = 10, capacitate r˘amas˘a: 5 − 1 = 4 kg. 2. iau 100% din al doilea obiect (deci p[1] = 1). Cˆas, tig: 10 + 1 × 15 = 25, capacitate r˘amas˘a: 4 − 2 = 2 kg. 3. iau 2/3 din al treilea obiect (deci p[2] = 0.66 . . .). Cˆas, tig: 25 + 2/3 × 20 = 38.33 . . .. O abordare greedy care conduce la solut, ia optim˘a este s˘a alegem cˆat mai mult din obiectul cu cˆas, tig unitar (cˆas, tig / kilogram) cel mai mare. Exercit¸iul 5. Identificat, i subproblemele pentru problema rucsacului - varianta continu˘a. Enunt, at, i s, i demonstrat, i lema de alegere greedy. Enunt, at, i proprietatea de substructur˘a optim˘a (s, i demonstrat, i-o, dar demonstrat, ia va fi surprinz˘ator de simpl˘a). Problema rucsacului - varianta discret˘ a Un hot, a spart un magazin ,si a g˘asit n bunuri. Al i-lea bun valoreaz˘a vi lei ant˘ares, te wi kilograme. Hot, ul are un rucsac care poate s˘a duc˘a cel mult W ,si cˆ kilograme de bunuri. Niciun bun nu poate fi sect, ionat - obiectul i trebuie furat integral sau deloc. Hot, ul vrea s˘a maximizeze valorea obiectelor pe care le va pune ˆın rucsac.

8

Problema rucsacului - formalizare varianta discret˘ a Input: n, v[0..n − 1], w[0..n − 1], W , toate numere naturale Output: p[0..n − 1], p[i] ∈ {0, 1} astfel ˆıncˆat: 1. Σi p[i]w[i] ≤ W

(obiectele ˆıncap ˆın rucsac)

2. Σi p[i]v[i] este maxim

(valoarea obiectelor este maxim˘a)

a Problema rucsacului - exemplu instant, ˘ Avem n = 3 obiecte: i w[i] v[i]

0 1 2 1 2 3 10 15 20

Rucsacul are capacitate de W = 5 kg. O solut, ie optim˘a pentru varianta discret˘a: 1. nu iau primul obie...