De ce contează sensul buclei la problema rucsacului
Compară actualizarea descrescătoare cu cea crescătoare într-un tablou de stări. Observă când un obiect poate fi reutilizat în aceeași etapă.
În acest material
În problema rucsacului, alegi obiecte respectând o capacitate și urmărești o valoare maximă. Varianta 0/1 permite fiecare obiect cel mult o dată. Varianta nelimitată permite repetarea unui tip de obiect. Sensul unei bucle poate decide exact această diferență.
Ce reprezintă o stare
Presupunem că dp[c] este cea mai bună valoare obținută pentru o capacitate disponibilă c, fără obligația de a o umple exact. Pentru un obiect cu greutate w și valoare v, o posibilă actualizare folosește dp[c-w]+v.
Întrebarea esențială este ce obiecte sunt deja permise în valoarea dp[c-w] pe care o citești. Dacă ea a fost actualizată chiar în etapa obiectului curent, acel obiect poate fi folosit din nou.
Parcurgerea crescătoare permite reutilizarea
Ia un singur obiect cu greutate 2 și valoare 3, la capacitatea 4. Dacă parcurgi capacitățile crescător, actualizezi dp[2] la 3. Mai târziu, dp[4] poate folosi acel dp[2] și devine 6.
Rezultatul folosește de două ori obiectul. Este potrivit pentru varianta nelimitată, dar greșit pentru varianta 0/1, în care valoarea maximă rămâne 3. Acest exemplu mic detectează direct sensul semantic al buclei.
Pentru un obiect cu greutate 2 și valoare 3, la capacitatea 4, parcurgerea crescătoare poate obține 6 reutilizând obiectul. Varianta 0/1 trebuie să rămână la 3.Mărește schema ↗
Parcurgerea descrescătoare păstrează etapa anterioară
În varianta 0/1, pentru fiecare obiect parcurgi capacitățile de la mare la mic. Când citești dp[c-w], acea capacitate mai mică nu a fost încă actualizată pentru obiectul curent. Astfel, tranziția adaugă obiectul o singură dată.
Explicația presupune greutăți strict pozitive. Obiectele cu greutate zero necesită un contract separat, mai ales în varianta nelimitată, unde o valoare pozitivă repetabilă poate face maximul nelimitat.
Inițializarea este o altă decizie
Dacă problema cere umplerea exactă a capacității, zero nu poate reprezenta toate stările inițiale accesibile. Trebuie să marchezi separat capacitățile imposibile. Sensul corect al buclei nu repară o definiție greșită a stării.
Înainte să comprimi o matrice de etape într-un singur tablou, scrie din ce etapă trebuie citită fiecare valoare. Această dependență explică direcția de parcurgere și te ajută și în alte probleme de programare dinamică.
Revezi introducerea în programarea dinamică, problema rucsacului și tablourile.
Întrebări frecvente
De ce parcurg capacitățile descrescător la rucsacul 0/1?
Astfel, actualizarea pentru obiectul curent folosește stări care nu l-au inclus deja. Fiecare obiect poate fi ales cel mult o dată, conform variantei 0/1.
De ce parcurg crescător capacitățile la rucsacul nelimitat?
O stare mai mică poate conține deja tipul curent de obiect. Refolosirea ei permite adăugarea încă unui exemplar, exact comportamentul cerut când numărul copiilor este nelimitat.
Contează dacă trebuie umplută exact capacitatea?
Da. Inițializarea cu zero a tuturor stărilor corespunde unei formulări cu greutate cel mult capacitatea și selecție goală permisă. Pentru umplere exactă trebuie reprezentate separat stările imposibile.