Actualizare: Citește despre optimizarea spațiului complexitatea programării dinamice soluție în follow-up articolul de aici.,
Problema Rucsacului este o problemă interesantă în combinatorică — pentru a cita Wikipedia,
„având în vedere un set de elemente, fiecare cu o greutate și o valoare, se determină numărul de fiecare element pentru a include într-o colecție, astfel încât greutatea totală este mai mică sau egală cu o anumită limită și valoarea totală este la fel de mare ca posibil.”
Din Wikipedia, vedem că există câteva variații ale problemei rucsacului: rucsacul 0-1, rucsacul delimitat și rucsacul nelimitat., Astăzi, ne vom concentra pe cea mai comună (și cea mai simplă) variație: problema rucsacului 0-1.
Un pic mai interesant și credibil formularea 0-1 problema rucsacului este:
Considera un hoț intră într-o casă să fure și el poartă un rucsac. Există un număr fix de articole în casă — fiecare cu propria greutate și valoare — bijuterii, cu o greutate mai mică și cu cea mai mare valoare față de tabele, cu o valoare mai mică, dar mult mai grea. Pentru a adăuga combustibil la foc, hoțul are un rucsac vechi care are o capacitate limitată., Evident, el nu poate împărți masa în jumătate sau bijuterii în 3/4ths. Ori o ia, ori o lasă. Sursa
Din păcate, am avut unele dificultăți în a înțelege unele părți ale articolului Hackerearth, motiv pentru care am decis să-mi scriu propriul articol. Acest articol se va baza în mare parte pe articolul Hackerearth și fragmente de cod sunt scrise în Java. Voi aborda explicații și elaborări suplimentare acolo unde simt că sunt necesare.
vom rezolva această problemă cu programarea dinamică., Programarea dinamică necesită o substructură optimă și subprobleme suprapuse, ambele fiind prezente în problema rucsacului 0-1, după cum vom vedea.
este bine dacă nu înțelegeți care sunt „substructura optimă” și „sub-problemele suprapuse” (acesta este un articol pentru o altă zi). În esență, înseamnă doar o aromă particulară a problemelor care ne permit să reutilizăm soluțiile anterioare la probleme mai mici pentru a calcula o soluție la problema actuală. Vei vedea ce vreau să spun într-un pic.,
detalii problemă
deoarece aceasta este problema rucsacului 0-1, putem fie să includem un articol în rucsacul nostru, fie să îl excludem, dar să nu includem o fracțiune din acesta sau să îl includem de mai multe ori.
Soluție
în Primul rând, vom crea o 2-dimensional array (de exemplu o masă) de n + 1 rânduri și w + 1 coloane.
un număr rând i reprezintă setul tuturor elementelor din rândurile 1-i. de exemplu, valorile din rândul 3 presupune că avem doar elementele 1, 2 și 3.
un număr de coloană j reprezintă capacitatea de greutate a rucsacului nostru., Prin urmare, valorile din coloana 5, de exemplu, presupun că rucsacul nostru poate conține 5 unități de greutate.
punând totul împreună, o intrare în rândul i, coloana j reprezintă valoarea maximă care poate fi obținută cu articolele 1, 2, 3 … i, într-un rucsac care poate conține unități de greutate J.
să numim tabelul nostru mat pentru matrice. Prin urmare, int mat = new int.
Pasul 2:
putem începe imediat completarea unor intrări în tabelul nostru: cazurile de bază, pentru care soluția este banală., De exemplu, la rândul 0, când nu avem elemente din care să alegem, valoarea maximă care poate fi stocată în orice rucsac trebuie să fie 0. În mod similar, la coloana 0, pentru un rucsac care poate conține unități de greutate 0, valoarea maximă care poate fi stocată în acesta este 0. (Presupunem că nu există obiecte de valoare fără masă.)
putem face asta cu 2 pentru bucle:
Pasul 3 (esența problemei):
Acum, ne-o dorim pentru a începe popularea masa noastră., Ca și în cazul tuturor soluțiilor de programare dinamică, la fiecare pas, vom folosi soluțiile noastre La sub-problemele anterioare.
voi descrie mai întâi logica, înainte de a arăta un exemplu concret.
relația dintre valoarea la rândul i, coloana j și valorile la sub-problemele anterioare este următoarea:
reamintim că la rândul i și coloana j abordăm o sub-problemă constând din elementele 1, 2, 3 … i cu un rucsac de capacitate J. Există opțiuni 2 în acest moment: putem include elementul i sau nu., Prin urmare, trebuie să comparăm valoarea maximă pe care o putem obține cu și fără elementul i.
valoarea maximă pe care o putem obține fără elementul i poate fi găsită la rândul i-1, coloana j. această parte este ușoară. Raționamentul este simplu: indiferent de valoarea maximă pe care o putem obține cu articolele 1, 2, 3 … trebuie să fie în mod evident aceeași valoare maximă pe care o putem obține cu articolele 1, 2, 3 … i – 1, dacă alegem să nu includem articolul i.
pentru a calcula valoarea maximă pe care o putem obține cu articolul i, trebuie mai întâi să comparăm greutatea articolului i cu capacitatea de greutate a rucsacului., Evident, dacă elementul i cântărește mai mult decât ceea ce poate ține rucsacul, nu îl putem include, deci nu are sens să efectuăm calculul. În acest caz, soluția la această problemă este pur și simplu valoarea maximă pe care o putem obține fără elementul i (adică valoarea din rândul de mai sus, în aceeași coloană).
cu toate acestea, să presupunem că elementul i cântărește mai puțin decât capacitatea rucsacului. Avem astfel opțiunea de a o include, dacă poate crește valoarea maximă obținută., Valoarea maximă obținută prin includerea articolului i este astfel = valoarea articolului i în sine + valoarea maximă care poate fi obținută cu capacitatea rămasă a rucsacului. Evident, vrem să folosim pe deplin capacitatea rucsacului nostru și să nu lăsăm nicio capacitate rămasă să se risipească.
prin urmare, la rândul i și coloana j (care reprezintă valoarea maximă pe care o putem obține acolo), am alege fie valoarea maximă pe care o putem obține fără elementul i, fie valoarea maximă pe care o putem obține cu elementul i, oricare dintre acestea este mai mare.
Iată un exemplu concret despre ceea ce vreau să spun.,
La randul 3 (punctul 2), și coloana 5 (rucsac capacitate de 4), putem alege să includă punctul 2 (care cantareste 4 unități), sau nu. Dacă alegem să nu o includem, valoarea maximă pe care o putem obține este aceeași ca și cum am avea doar elementul 1 din care să alegem (care se găsește în rândul de mai sus, adică 0)., Dacă dorim să includem articolul 2, valoarea maximă pe care o putem obține cu articolul 2 este valoarea articolului 2 (40) + valoarea maximă pe care o putem obține cu capacitatea rămasă (care este 0, deoarece rucsacul este deja complet plin).
la rândul 3 (Articolul 2) și coloana 10 (capacitatea rucsacului de 9), din nou, putem alege să includem elementul 2 sau nu. Dacă alegem să nu, valoarea maximă pe care o putem obține este aceeași cu cea din rândul de mai sus din aceeași coloană, adică 10 (prin includerea numai a articolului 1, care are o valoare de 10). Dacă includem articolul 2, avem o capacitate de rucsac rămasă de 9-4 = 5., Putem afla valoarea maximă care poate fi obținută cu o capacitate de 5 uitându-ne la rândul de mai sus, la coloana 5. Astfel, valoarea maximă pe care o putem obține prin includerea articolului 2 este 40 (valoarea articolului 2) + 10 = 50.
alegem cea mai mare dintre 50 vs 10, astfel încât valoarea maximă pe care o putem obține cu articolele 1 și 2, cu o capacitate de rucsac de 9, este 50.,
algoritmul poate fi exprimat în Java astfel:
Pasul 4 (soluția finală):
după ce masa a fost populat, soluția finală poate fi găsit la ultimul rând din ultima coloana, care reprezintă valoarea maximă obținută cu toate elementele și capacitate deplină de rucsac.
return mat;
cod de lucru:
notă: aici, am tipărit răspunsul final în loc să-l returnez, deoarece totul este găzduit sub void static public principal.,
Thanks for reading!