Rucsacul 0/1 cu tabel 1D parcurs crescător folosește același obiect de mai multe ori
În rucsacul 0/1 cu un singur rând dp, dacă parcurgi capacitățile crescător, dp[w - g] e deja actualizat cu obiectul curent, deci obiectul e pus de mai multe ori. Parcurge capacitatea descrescător: for w in range(C, g - 1, -1).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Rucsacul 0/1 („fiecare obiect cel mult o dată”) se rezolvă cu un tabel dp[w] = valoarea maximă cu capacitatea w. Pentru fiecare obiect cu greutatea g și valoarea v: dp[w] = max(dp[w], dp[w - g] + v). Formula presupune că dp[w - g] e valoarea fără obiectul curent.
Dacă parcurgi w crescător, când ajungi la w, poziția w - g a fost deja actualizată în aceeași iterație, deci poate conține deja obiectul. Obiectul e adăugat din nou: rezultatul e cel al rucsacului nelimitat (fiecare obiect de oricâte ori), mai mare decât cel corect.
Parcurgând descrescător, dp[w - g] e încă valoarea de la obiectul anterior. Cu tabel 2D (dp[i][w]) problema nu apare, pentru că citești explicit rândul anterior.
De ce apare: cauzele frecvente
1Capacitatea parcursă crescător
for g, v in obiecte:
for w in range(g, C + 1):
dp[w] = max(dp[w], dp[w - g] + v)for g, v in obiecte:
for w in range(C, g - 1, -1):
dp[w] = max(dp[w], dp[w - g] + v)De la capacitatea mare la cea mică, dp[w - g] nu a fost încă atins de obiectul curent.
2Problema e de fapt cu obiecte nelimitate
for g, v in obiecte:
for w in range(C, g - 1, -1):
dp[w] = max(dp[w], dp[w - g] + v)for g, v in obiecte:
for w in range(g, C + 1):
dp[w] = max(dp[w], dp[w - g] + v)La problema monedelor sau la rucsacul nelimitat, refolosirea e dorită, deci ordinea crescătoare e cea corectă. Citește enunțul.
Repară eroarea, direct în pagină
Funcția rucsac(obiecte, C) calculează valoarea maximă a obiectelor (greutate, valoare) care încap în capacitatea C, fiecare obiect cel mult o dată. Testul cu assert pică: rezultatul e prea mare. Repar-o ca testele să treacă și să afișeze 4, 7 și 0.
def rucsac(obiecte, C):
dp = [0] * (C + 1)
for g, v in obiecte:
for w in range(g, C + 1):
dp[w] = max(dp[w], dp[w - g] + v)
return dp[C]
obiecte = [(2, 3), (3, 4)]
for C, corect in [(4, 4), (5, 7), (1, 0)]:
rez = rucsac(obiecte, C)
assert rez == corect, f'valoare gresita pentru C={C}: {rez}'
print(rez)4 7 0
Indiciu
Parcurge capacitatea de la C în jos până la greutatea obiectului.
Reparația
def rucsac(obiecte, C):
dp = [0] * (C + 1)
for g, v in obiecte:
for w in range(C, g - 1, -1):
dp[w] = max(dp[w], dp[w - g] + v)
return dp[C]
obiecte = [(2, 3), (3, 4)]
for C, corect in [(4, 4), (5, 7), (1, 0)]:
rez = rucsac(obiecte, C)
assert rez == corect, f'valoare gresita pentru C={C}: {rez}'
print(rez)De ce merge
Cu parcurgerea crescătoare, pentru capacitatea 4 codul citea dp[2], care tocmai primise obiectul de greutate 2, și îl mai adăuga o dată: valoarea 6, cu același obiect pus de două ori. Parcurgând descrescător, dp[2] e încă 0 când calculăm dp[4], deci fiecare obiect se folosește cel mult o dată. Pentru capacitatea 4, cel mai bun e obiectul de valoare 4; pentru 5, ambele obiecte.
Cum o eviți pe viitor
Pentru fiecare DP cu un singur rând, întreabă-te: „când citesc dp[x], am nevoie de valoarea veche sau de cea nouă?”. Rucsac 0/1 și numărarea submulțimilor: descrescător. Rucsac nelimitat și numărarea combinațiilor de monede: crescător. Dacă nu ești sigur, scrie întâi varianta 2D, verific-o, apoi compactează la 1D.
Întrebări frecvente
De ce nu primesc nicio eroare?
Pentru că toți indicii sunt valizi. Doar ordinea în care se suprascriu valorile schimbă sensul tabelului.
Ce complexitate are?
O(n · C) timp și O(C) memorie, unde n e numărul de obiecte și C capacitatea. Varianta 2D are aceeași viteză, dar O(n · C) memorie.
Erori înrudite
Restul minim cu monede iese 0: tabelul DP e inițializat cu 0 în loc de infinit La un DP de minim (cele mai puține monede), valoarea inițială trebuie să fie „imposibil” (float('inf')), nu 0, pentru că min(0, orice) rămâne 0. Pornește cu dp = [float('inf')] * (suma + 1), dp[0] = 0, iar la final returnează -1 dacă dp[suma] e tot infinit. IndexError: list index out of range la dp[n] (tabelul DP e prea scurt) Ai creat tabelul cu dp = [0] * n, dar răspunsul e dp[n], iar o listă cu n elemente are doar indicii 0..n-1. Când dp[i] înseamnă „primele i elemente” sau „treapta i”, tabelul are nevoie de n + 1 poziții: dp = [0] * (n + 1). Memo greșit: cheia nu conține toți parametrii, iar rezultatul e greșit Ai salvat în memo rezultatul doar după i (memo[i]), dar funcția depinde și de alt parametru (capacitate, j, suma rămasă), așa că un rezultat calculat pentru o stare e refolosit pentru alta. Cheia memo-ului trebuie să conțină toți parametrii care schimbă rezultatul: memo[(i, capacitate)]. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
