Aici rucsacul este ca un recipient sau o pungă. Să presupunem că am dat niște articole care au anumite ponderi sau profituri. Trebuie să punem unele articole în rucsac astfel încât valoarea totală să producă un profit maxim.

De exemplu, greutatea containerului este de 20 kg. Trebuie să selectăm articolele în așa fel încât suma greutății articolelor să fie fie mai mică, fie egală cu greutatea containerului, iar profitul să fie maxim.

Există două tipuri de probleme la rucsac:

• 0/1 problema la rucsac
• Problemă la rucsac fracționat

Vom discuta ambele probleme una câte una. În primul rând, vom afla despre problema rucsacului 0/1.

Care este problema rucsacului 0/1?

Problema rucsacului 0/1 înseamnă că articolele sunt fie complet, fie că niciun element nu este umplut într-un rucsac. De exemplu, avem două articole cu greutăți de 2 kg și, respectiv, 3 kg. Dacă alegem articolul de 2 kg, atunci nu putem alege un articol de 1 kg din articolul de 2 kg (articolul nu este divizibil); trebuie să alegem complet articolul de 2 kg. Aceasta este o problemă de rucsac 0/1 în care fie alegem articolul complet, fie îl vom alege. Problema rucsacului 0/1 este rezolvată prin programarea dinamică.

Care este problema rucsacului fracționat?

Problema rucsacului fracționat înseamnă că putem împărți articolul. De exemplu, avem un articol de 3 kg, apoi putem alege articolul de 2 kg și lăsam articolul de 1 kg. Problema rucsacului fracționat este rezolvată prin abordarea Greedy.

Exemplu de problemă la rucsac 0/1.

Luați în considerare problema având ponderi și profituri sunt:

Greutăți: {3, 4, 6, 5}

Profituri: {2, 3, 1, 4}

Greutatea rucsacului este de 8 kg

Numărul de articole este 4

Problema de mai sus poate fi rezolvată folosind următoarea metodă:

X_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

tipuri de arbore binar

= {0, 1, 0, 1}

Cele de mai sus sunt combinațiile posibile. 1 indică faptul că articolul este ales complet și 0 înseamnă că nu este ales niciun articol. Deoarece există 4 articole, combinațiile posibile vor fi:

2⁴= 16; Asa de. Există 16 combinații posibile care pot fi făcute folosind problema de mai sus. Odată realizate toate combinațiile, trebuie să selectăm combinația care oferă profitul maxim.

O altă abordare pentru a rezolva problema este abordarea de programare dinamică. În abordarea de programare dinamică, problema complicată este împărțită în sub-probleme, apoi găsim soluția unei sub-probleme și soluția sub-problemei va fi folosită pentru a găsi soluția unei probleme complexe.

Cum poate fi rezolvată această problemă prin utilizarea abordării de programare dinamică?

Primul,

creăm o matrice prezentată mai jos:

În matricea de mai sus, coloanele reprezintă ponderea, adică 8. Rândurile reprezintă profiturile și ponderile articolelor. Aici nu am luat direct ponderea 8, problema este împărțită în sub-probleme, adică 0, 1, 2, 3, 4, 5, 6, 7, 8. Rezolvarea sub-problemelor ar fi salvată în celulele și răspunsul la problemă ar fi stocat în celula finală. Mai întâi, scriem ponderile în ordine crescătoare și profiturile în funcție de ponderile lor prezentate mai jos:

În_i= {3, 4, 5, 6}

p_i= {2, 3, 4, 1}

Primul rând și prima coloană ar fi 0, deoarece nu există niciun element pentru w=0

Când i=1, W=1

În₁= 3; Deoarece avem un singur articol în set având greutatea 3, dar capacitatea rucsacului este de 1. Nu putem umple articolul de 3 kg în rucsac cu o capacitate de 1 kg, așa că adăugați 0 la M[1][1] prezentat mai jos. :

Când i = 1, W = 2

În₁= 3; Deoarece avem un singur articol în set având greutatea 3, dar capacitatea rucsacului este de 2. Nu putem umple articolul de 3 kg în rucsac cu o capacitate de 2 kg, așa că adăugați 0 la M[1][2] prezentat mai jos. :

Când i=1, W=3

În₁= 3; Deoarece avem un singur articol în set având greutatea egală cu 3, iar greutatea rucsacului este de asemenea 3; prin urmare, putem umple rucsacul cu un articol de greutate egal cu 3. Punem profitul corespunzător greutății 3, adică 2 la M[1][3] prezentat mai jos:

Când i=1, W = 4

_W1= 3; Deoarece avem un singur articol în set având greutatea egală cu 3, iar greutatea rucsacului este de 4; prin urmare, putem umple rucsacul cu un articol de greutate egal cu 3. Punem profitul corespunzător greutății 3, adică 2 la M[1][4] prezentat mai jos:

Când i=1, W = 5

_W1= 3; Deoarece avem un singur articol în set având o greutate egală cu 3, iar greutatea rucsacului este de 5; prin urmare, putem umple rucsacul cu un articol de greutate egal cu 3. Punem profitul corespunzător greutății 3, adică 2 la M[1][5] prezentat mai jos:

Când i =1, W=6

_W1= 3; Deoarece avem un singur articol în set având o greutate egală cu 3, iar greutatea rucsacului este de 6; prin urmare, putem umple rucsacul cu un articol de greutate egal cu 3. Punem profitul corespunzător greutății 3, adică 2 la M[1][6] prezentat mai jos:

Când i=1, W = 7

_W1= 3; Deoarece avem un singur articol în set având o greutate egală cu 3, iar greutatea rucsacului este de 7; prin urmare, putem umple rucsacul cu un articol de greutate egală cu 3. Punem profitul corespunzător greutății 3, adică 2 la M[1][7] prezentat mai jos:

Când i =1, W =8

_W1= 3; Deoarece avem un singur articol în set având o greutate egală cu 3, iar greutatea rucsacului este de 8; prin urmare, putem umple rucsacul cu un articol de greutate egal cu 3. Punem profitul corespunzător greutății 3, adică 2 la M[1][8] prezentat mai jos:

Acum valoarea lui „i” crește și devine 2.

Când i = 2, W = 1

Greutatea corespunzătoare valorii 2 este 4, adică w₂= 4. Deoarece avem un singur articol în set având greutate egală cu 4, iar greutatea rucsacului este 1. Nu putem pune articolul cu greutatea 4 într-un rucsac, așa că adăugăm 0 la M[2][1 ] prezentate după cum urmează:

Când i = 2, W = 2

Greutatea corespunzătoare valorii 2 este 4, adică w₂= 4. Deoarece avem un singur articol în set având greutate egală cu 4, iar greutatea rucsacului este 2. Nu putem pune articolul cu greutatea 4 într-un rucsac, așa că adăugăm 0 la M[2][2 ] prezentate după cum urmează:

Când i = 2, W = 3

Greutatea corespunzătoare valorii 2 este 4, adică w₂= 4. Deoarece avem două articole în set având greutățile 3 și 4, iar greutatea rucsacului este 3. Putem pune articolul cu greutatea 3 într-un rucsac, așa că adăugăm 2 la M[2][3] prezentate după cum urmează:

Când i = 2, W = 4

Greutatea corespunzătoare valorii 2 este 4, adică w₂= 4. Deoarece avem două articole în set având greutățile 3 și 4, iar greutatea rucsacului este 4. Putem pune articolul cu greutatea 4 într-un rucsac deoarece profitul corespunzător greutății 4 este mai mare decât articolul cu greutate 3, deci adăugăm 3 la M[2][4] arătat mai jos:

Când i = 2, W = 5

Greutatea corespunzătoare valorii 2 este 4, adică w₂= 4. Deoarece avem două articole în set având greutățile 3 și 4, iar greutatea rucsacului este 5. Putem pune articolul cu greutatea 4 într-un rucsac și profitul corespunzător greutății este 3, așa că adăugăm 3 la M[2][5] prezentat mai jos:

Când i = 2, W = 6

Greutatea corespunzătoare valorii 2 este 4, adică w₂= 4. Deoarece avem două articole în set având greutăți 3 și 4, iar greutatea rucsacului este 6. Putem pune articolul cu greutatea 4 într-un rucsac și profitul corespunzător greutății este 3, așa că adăugăm 3 la M[2][6] prezentat mai jos:

Când i = 2, W = 7

Greutatea corespunzătoare valorii 2 este 4, adică w₂= 4. Întrucât avem două articole în set având greutățile 3 și 4, iar greutatea rucsacului este 7. Putem pune obiectele cu greutatea 4 și 3 într-un rucsac și profiturile corespunzătoare greutăților sunt 2 și 3; prin urmare, profitul total este 5, așa că adăugăm 5 la M[2][7] prezentat mai jos:

Când i = 2, W = 8

Greutatea corespunzătoare valorii 2 este 4, adică w₂= 4. Întrucât avem două articole în set având greutățile 3 și 4, iar greutatea rucsacului este 7. Putem pune obiectele cu greutatea 4 și 3 într-un rucsac și profiturile corespunzătoare greutăților sunt 2 și 3; prin urmare, profitul total este 5, așa că adăugăm 5 la M[2][7] prezentat mai jos:

Acum valoarea lui „i” crește și devine 3.

Când i = 3, W = 1

java main

Greutatea corespunzătoare valorii 3 este 5, adică w₃= 5. Deoarece avem trei articole în mulțime având greutăți 3, 4 și 5, iar greutatea rucsacului este 1. Nu putem pune niciunul dintre articole într-un rucsac, așa că adăugăm 0 la M[3][ 1] prezentate după cum urmează:

Când i = 3, W = 2

Greutatea corespunzătoare valorii 3 este 5, adică w₃= 5. Deoarece avem trei articole în mulțime având greutatea 3, 4 și 5, iar greutatea rucsacului este 1. Nu putem pune niciunul dintre articole într-un rucsac, așa că adăugăm 0 la M[3][ 2] prezentate după cum urmează:

Când i = 3, W = 3

Greutatea corespunzătoare valorii 3 este 5, adică w₃= 5. Deoarece avem trei articole în setul de greutate 3, 4 și, respectiv, 5 și greutatea rucsacului este 3. Articolul cu greutatea 3 poate fi pus în rucsac și profitul corespunzător articolului este 2, deci adăugăm 2 la M[3][3] arătat mai jos:

Când i = 3, W = 4

Greutatea corespunzătoare valorii 3 este 5, adică w₃= 5. Deoarece avem trei articole în setul de greutate 3, 4 și, respectiv, 5, iar greutatea rucsacului este 4. Putem păstra articolul cu greutatea 3 sau 4; profitul (3) corespunzător ponderii 4 este mai mare decât profitul corespunzător ponderii 3, așa că adăugăm 3 la M[3][4] prezentat mai jos:

Când i = 3, W = 5

alternative watchcartoononline.io

Greutatea corespunzătoare valorii 3 este 5, adică w₃= 5. Deoarece avem trei articole în setul de greutăți 3, 4 și, respectiv, 5, iar greutatea rucsacului este 5. Putem păstra articolul cu greutatea 3, 4 sau 5; profitul (3) corespunzător ponderii 4 este mai mare decât profiturile corespunzătoare ponderii 3 și 5, așa că adăugăm 3 la M[3][5] arătat mai jos:

Când i = 3, W = 6

Greutatea corespunzătoare valorii 3 este 5, adică w₃= 5. Deoarece avem trei articole în setul de greutăți 3, 4 și, respectiv, 5, iar greutatea rucsacului este 6. Putem păstra articolul cu greutatea 3, 4 sau 5; profitul (3) corespunzător ponderii 4 este mai mare decât profiturile corespunzătoare ponderii 3 și 5, așa că adăugăm 3 la M[3][6] prezentate mai jos:

Când i = 3, W = 7

Greutatea corespunzătoare valorii 3 este 5, adică w₃= 5. Deoarece avem trei articole în setul de greutate 3, 4 și, respectiv, 5, iar greutatea rucsacului este 7. În acest caz, putem păstra atât articolele cu greutatea 3, cât și 4, suma profitului. ar fi egal cu (2 + 3), adică 5, deci adăugăm 5 la M[3][7] prezentat mai jos:

Când i = 3, W = 8

Greutatea corespunzătoare valorii 3 este 5, adică w₃= 5. Deoarece avem trei articole în setul de greutate 3, 4 și, respectiv, 5, iar greutatea rucsacului este 8. În acest caz, putem păstra atât elementele cu greutatea 3, cât și 4, suma profitul ar fi egal cu (2 + 3), adică 5, deci adăugăm 5 la M[3][8] prezentat mai jos:

Acum valoarea lui „i” crește și devine 4.

Când i = 4, W = 1

Greutatea corespunzătoare valorii 4 este 6, adică w₄= 6. Deoarece avem patru articole în setul de greutăți 3, 4, 5 și, respectiv, 6, iar greutatea rucsacului este 1. Greutatea tuturor articolelor este mai mare decât greutatea rucsacului, deci nu putem adăugați orice articol în rucsac; Prin urmare, adăugăm 0 la M[4][1] arătat mai jos:

Când i = 4, W = 2

Greutatea corespunzătoare valorii 4 este 6, adică w₄= 6. Deoarece avem patru articole în setul de greutăți 3, 4, 5 și, respectiv, 6, iar greutatea rucsacului este 2. Greutatea tuturor articolelor este mai mare decât greutatea rucsacului, deci nu putem adăugați orice articol în rucsac; Prin urmare, adăugăm 0 la M[4][2] arătat mai jos:

Când i = 4, W = 3

Greutatea corespunzătoare valorii 4 este 6, adică w₄= 6. Deoarece avem patru articole în setul de greutăți 3, 4, 5 și, respectiv, 6, iar greutatea rucsacului este 3. Articolul cu greutatea 3 poate fi pus în rucsac și profitul corespunzător greutatea 4 este 2, așa că vom adăuga 2 la M[4][3] prezentată mai jos:

Când i = 4, W = 4

Greutatea corespunzătoare valorii 4 este 6, adică w₄= 6. Deoarece avem patru articole în setul de greutăți 3, 4, 5 și, respectiv, 6, iar greutatea rucsacului este 4. Articolul cu greutatea 4 poate fi pus în rucsac și profitul corespunzător greutatea 4 este 3, așa că vom adăuga 3 la M[4][4] prezentată mai jos:

Când i = 4, W = 5

Greutatea corespunzătoare valorii 4 este 6, adică w₄= 6. Deoarece avem patru articole în setul de greutăți 3, 4, 5 și, respectiv, 6, iar greutatea rucsacului este 5. Articolul cu greutatea 4 poate fi pus în rucsac și profitul corespunzător greutatea 4 este 3, așa că vom adăuga 3 la M[4][5] prezentată mai jos:

Când i = 4, W = 6

Greutatea corespunzătoare valorii 4 este 6, adică w₄= 6. Deoarece avem patru articole în setul de greutăți 3, 4, 5 și, respectiv, 6, iar greutatea rucsacului este 6. În acest caz, putem pune articolele în rucsac fie cu greutatea 3, 4. , 5 sau 6, dar profitul, adică 4 corespunzător ponderii 6 este cel mai mare dintre toate articolele; prin urmare, adăugăm 4 la M[4][6] arătat mai jos:

Când i = 4, W = 7

Greutatea corespunzătoare valorii 4 este 6, adică w₄= 6. Deoarece avem patru articole în setul de greutăți 3, 4, 5 și, respectiv, 6, iar greutatea rucsacului este 7. Aici, dacă adăugăm două articole de greutăți 3 și 4, atunci se va produce maximul profitul, adică (2 + 3) este egal cu 5, deci adăugăm 5 la M[4][7] arătat mai jos:

Când i = 4, W = 8

Greutatea corespunzătoare valorii 4 este 6, adică w₄= 6. Deoarece avem patru articole în setul de greutăți 3, 4, 5 și, respectiv, 6, iar greutatea rucsacului este 8. Aici, dacă adăugăm două articole de greutăți 3 și 4, atunci se va produce maximul profit, adică (2 + 3) este egal cu 5, deci adăugăm 5 la M[4][8], prezentat mai jos:

După cum putem observa în tabelul de mai sus, 5 este profitul maxim dintre toate înregistrările. Pointerul indică ultimul rând și ultima coloană având valoarea 5. Acum vom compara valoarea 5 cu rândul anterior; dacă rândul anterior, adică i = 3, conține aceeași valoare 5, atunci indicatorul se va deplasa în sus. Deoarece rândul anterior conține valoarea 5, indicatorul va fi deplasat în sus, așa cum se arată în tabelul de mai jos:

Din nou, vom compara valoarea 5 din rândul de mai sus, adică i = 2. Deoarece rândul de mai sus conține valoarea 5, indicatorul va fi din nou deplasat în sus, așa cum se arată în tabelul de mai jos:

Din nou, vom compara valoarea 5 din rândul de mai sus, adică i = 1. Deoarece rândul de mai sus nu conține aceeași valoare, vom lua în considerare rândul i=1, iar greutatea corespunzătoare rândului este 4. Prin urmare , am selectat greutatea 4 și am respins greutățile 5 și 6 prezentate mai jos:

x = { 1, 0, 0}

Profitul corespunzător ponderii este 3. Prin urmare, profitul rămas este (5 - 3) egal cu 2. Acum vom compara această valoare 2 cu rândul i = 2. Deoarece rândul (i = 1) conține valoarea 2 ; prin urmare, indicatorul s-a deplasat în sus, prezentat mai jos:

Din nou comparăm valoarea 2 cu un rând de mai sus, adică i = 1. Deoarece rândul i =0 nu conține valoarea 2, deci rândul i = 1 va fi selectat și greutatea corespunzătoare i = 1 este afișată 3. de mai jos:

X = {1, 1, 0, 0}

Profitul corespunzător ponderii este 2. Prin urmare, profitul rămas este 0. Compară 0 valoare cu rândul de mai sus. Deoarece rândul de mai sus conține o valoare 0, dar profitul corespunzător acestui rând este 0. În această problemă, sunt selectate două ponderi, adică 3 și 4 pentru a maximiza profitul.