...
Eroare Algoritmi și structuri de date · Programare dinamică și memoizare

Rucsacul 0/1 cu tabel 1D parcurs crescător folosește același obiect de mai multe ori

Pe scurt

Î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

Greșit
PYTHON
for g, v in obiecte:
    for w in range(g, C + 1):
        dp[w] = max(dp[w], dp[w - g] + v)
Corect
PYTHON
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

Greșit
PYTHON
for g, v in obiecte:
    for w in range(C, g - 1, -1):
        dp[w] = max(dp[w], dp[w - g] + v)
Corect
PYTHON
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ă tu

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.

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
4
7
0
Indiciu

Parcurge capacitatea de la C în jos până la greutatea obiectului.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.