În acest tutorial, mai devreme am discutat Fracționată problema Rucsacului cu ajutorul Lacom abordare. Am arătat că abordarea lacomă oferă o soluție optimă pentru rucsacul fracționat. Cu toate acestea, acest capitol va acoperi problema rucsacului 0-1 și analiza acestuia.
în rucsacul 0-1, articolele nu pot fi rupte, ceea ce înseamnă că hoțul ar trebui să ia articolul în ansamblu sau ar trebui să-l lase., Acesta este motivul din spatele numindu-l ca 0-1 Rucsac.prin urmare, în cazul rucsacului 0-1, valoarea xi poate fi 0 sau 1, Unde alte constrângeri rămân aceleași.
0-1 rucsacul nu poate fi rezolvat prin abordarea lacomă. Abordarea lacomă nu asigură o soluție optimă. În multe cazuri, abordarea lacomă poate oferi o soluție optimă.următoarele exemple vor stabili Declarația noastră.
exemplu-1
să considerăm că capacitatea rucsacului este W = 25, iar elementele sunt așa cum se arată în tabelul următor.,
| Element | Un | B | C | D |
|---|---|---|---|---|
| Profit | 24 | 18 | 18 | 10 |
| Greutate | 24 | 10 | 10 | 7 |
Fără a ține cont de profit pe unitatea de greutate (pi/wi), dacă vom aplica Lacom abordare pentru a rezolva această problemă, primul element va fi selectat ca acesta va contribui profit maxim dintre toate elementele.,
după selectarea articolului A, nu va mai fi selectat niciun element. Prin urmare, pentru acest set dat de articole profitul total este de 24. Întrucât, soluția optimă poate fi obținută prin selectarea elementelor, B și C, unde profitul total este 18 + 18 = 36.
exemplu-2
în loc să selectați elementele pe baza beneficiului general, în acest exemplu elementele sunt selectate pe baza raportului pi/wi. Să considerăm că capacitatea rucsacului este W = 60, iar elementele sunt așa cum se arată în tabelul următor.,
| Item | A | B | C |
|---|---|---|---|
| Price | 100 | 280 | 120 |
| Weight | 10 | 40 | 20 |
| Ratio | 10 | 7 | 6 |
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380., Cu toate acestea, soluția optimă a acestei instanțe poate fi obținută prin selectarea elementelor, B și C, unde profitul total este de 280 + 120 = 400.prin urmare, se poate concluziona că abordarea lacomă nu poate oferi o soluție optimă.pentru a rezolva rucsacul 0-1, este necesară o abordare dinamică de programare.
declarație problemă
Un hoț jefuiește un magazin și poate transporta o greutate maximă de W în rucsac. Există n elemente și greutatea ith element este wi și profitul de a selecta acest element este pi. Ce elemente ar trebui să ia hoțul?,
abordarea programării dinamice
să fiu elementul cu cel mai mare număr într-o soluție optimă S pentru dolari W. Apoi S ‘ = s – {i} este o soluție optimă pentru dolari W – wi, iar valoarea soluției S este Vi plus valoarea sub-problemei.putem exprima acest fapt în următoarea formulă: definiți c pentru a fi soluția pentru articolele 1,2,…, i și greutatea maximă w.,
algoritmul are următoarele intrări
-
greutate maxima W
-
numărul de elemente n
-
Cele două secvențe v = <v1, v2, …, vn> și w = <w1, w2, …, wn>
setul de elemente pentru a lua poate fi dedus din tabel, pornind de la c și contur înapoi în cazul în care valorile optime a venit de la.
analiză
acest algoritm ia θ (n, w) ori ca tabelul c are (n + 1).(w + 1) intrări, în cazul în care fiecare intrare necesită θ (1) timp pentru a calcula.,