problema rucsacului
am găsit problema rucsacului complicată și interesantă în același timp. Sunt sigur că, dacă vizitați această pagină, știți deja problema declarație, dar doar de dragul de finalizare :
Problema:
Dat un Rucsac cu o capacitate maximă de W și N elemente, fiecare cu propria sa valoare și greutate, arunca în articole în Rucsac astfel încât conținutul final are valoarea maximă. Yikes !!,
iată modul general în care este explicată problema – luați în considerare un hoț intră într-o casă pentru a jefui și 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., El are sau lasă-l
Exemplu :
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
O privire sumară, la date de exemplu ne spune că valoarea maximă pe care ne-ar putea găzdui cu limita de greutate max de 10 este de 50 + 40 = 90, cu o greutate de 7.modul în care acest lucru este rezolvat în mod optim este utilizarea programării dinamice – rezolvarea pentru seturi mai mici de probleme cu rucsacul și apoi extinderea acestora pentru problema mai mare.,
să construim o matrice Item X Weight numită V (Value array):
V = 4 rows * 10 columnsfiecare dintre valorile din această matrice reprezintă o problemă mai mică a rucsacului.
cazul de bază 1: Să luăm cazul coloanei 0. Înseamnă doar că rucsacul are o capacitate de 0. Ce poți ține în ele? Nimic. Deci, să le umplem pe toate cu 0s.
cazul de bază 2 : Să luăm cazul rândului 0. Înseamnă doar că nu există obiecte în casă. Ce țineți în rucsac dacă nu există articole. Nimic din nou !!! Toate zerouri.,
soluție:
1) acum, să începem să completăm matricea rând-înțelept. Ce înseamnă rândul 1 și coloana 1? Acest lucru având în vedere primul element( rând), puteți să-l găzdui în rucsac cu capacitate 1 (coloană). Nope. Greutatea primului element este de 5. Deci, să completăm 0. De fapt, nu am putea completa nimic până nu ajungem la coloana 5 (greutatea 5).
2) Odată ce ajungem la coloana 5 (care reprezintă greutatea 5) pe primul rând, înseamnă că am putea găzdui elementul 1., Să umple în 10 (amintiți-vă, aceasta este o Valoare matrice):
3) se Deplasează pe, pentru greutate, 6 (coloana 6), putem găzdui orice altceva cu restul de greutate de 1 (greutatea – de acest element => 6 – 5). Hei, amintiți-vă, suntem pe primul element. Deci, este un fel de intuitiv că restul rândului va fi doar aceeași valoare prea, deoarece nu suntem în măsură să adăugați în orice alt element pentru că greutatea in plus pe care le-am luat.,
4) deci, următorul lucru interesant se întâmplă când ajungem la coloana 4 din al treilea rând. Greutatea curentă de rulare este 4.
ar trebui să verificăm următoarele cazuri.
1) putem găzdui elementul 2 – da, putem. Greutatea articolului 2 este 4.
2) este valoarea pentru greutatea curentă este mai mare fără elementul 2? – Verificați rândul anterior pentru aceeași greutate. Nope. rândul anterior * are 0 în el, deoarece nu am putut găzdui elementul 1 în greutate 4.3) putem găzdui două elemente în aceeași greutate, astfel încât să putem maximiza valoarea? – Nu., Greutatea rămasă după deducerea Item2 greutatea este 0.
De ce rândul anterior?
pur și simplu pentru că rândul anterior la greutatea 4 în sine este o soluție de rucsac mai mică, care dă valoarea maximă care ar putea fi acumulată pentru acea greutate până în acel punct (traversarea prin articole).,
exemplificând,
1) valoarea elementului curent = 40
2) greutatea elementului curent = 4
3) greutatea rămasă = 4 – 4 = 0
4) Verificați rândul de mai sus (elementul de mai sus în cazul articolului 1 sau valoarea maximă cumulată în cazul restului rândurilor). Pentru greutatea rămasă 0, putem găzdui elementul 1? Pur și simplu, există vreo valoare în rândul de mai sus pentru greutatea dată?,
calculul decurge astfel :
1) să Ia valoarea maximă pentru aceeași greutate, fără acest element:
previous row, same weight = 0=> V2) Ia valoarea de elementul curent + valoarea pe care ne-am putea potrivi cu restul greutate:
Max între cele două este de 40 (0 și 40).
3) Următorul și cel mai important eveniment se întâmplă la coloana 9 și rândul 2. Adică avem o greutate de 9 și avem două elemente. Privind datele de exemplu, am putea găzdui primele două elemente., Aici, considerăm câteva lucruri:
- valoarea elementului curent = 40
- greutatea elementului curent = 4
- greutatea rămasă = 9 – 4 = 5
- verificați rândul de mai sus. La greutatea rămasă 5, putem găzdui elementul 1.
Deci, calculul este :
1) să Ia valoarea maximă pentru aceeași greutate, fără acest element:
previous row, same weight = 102) Ia valoarea de elementul curent + valoarea pe care ne-ar putea acumula cu restul de greutate:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,la sfârșitul rezolvării tuturor acestor probleme mai mici, trebuie doar să returnăm valoarea la V-Item 4 la greutatea 10:
complexitatea
analiza complexității soluției este destul de simplă. Avem doar o buclă pentru W într-o buclă de N = > o (NW)
implementare:
aici vine codul de implementare obligatoriu în Java: