...
← Curs Algoritmi pentru interviuri
Lecțiile 126–150

Continuă cu Programare dinamică și interviuri simulate

Primele 2 lecții din Curs Algoritmi pentru interviuri sunt gratuite, fără card. Începe cu ele și vezi dacă ți se potrivește înainte să plătești ceva.

Începe gratuit de la lecția 1 →

Academia Programatorilor
Diplomă de absolvire Seria PREVIZUALIZARE

Se certifică faptul că

Numele tău

a absolvit integral Curs Algoritmi pentru interviuri, cu toate cele 150 de lecții interactive finalizate și exercițiile verificate automat.

Diplomă Algoritmi pentru interviuri
Tudor Dumitrescu Tudor Dumitrescu Fondator · Trainer & formator autorizat
Data emiterii 19 noiembrie 2026 Verificare online academiaprogramatorilor.ro/certificat/PREVIZUALIZARE/
La finalul modulului primești Diplomă Algoritmi pentru interviuri
Lecția 136 · Programare dinamică și interviuri simulate

Problema rucsacului 0/1

Pleci într-o drumeție cu un rucsac care duce cel mult 7 kg. Ai mai multe obiecte, fiecare cu o greutate și o valoare (cât de util îți este). Pe fiecare îl iei întreg sau deloc. Ce iei ca valoarea totală să fie maximă? Problema rucsacului 0/1 este modelul pentru zeci de probleme de interviu cu „buget limitat”.

Problema

Primești listele greutati și valori (obiectul i are greutatea greutati[i] și valoarea valori[i]) și capacitate. Alegi o submulțime de obiecte cu greutatea totală cel mult capacitate și valoarea totală maximă. Fiecare obiect se poate lua cel mult o dată (de aici „0/1”).

Exercițiul lecției

Scrie funcția rucsac(greutati, valori, capacitate) care returnează valoarea maximă a obiectelor care încap în rucsac (fiecare obiect cel mult o dată), cu programare dinamică. Testele sunt deja scrise.

  • Creează un rând dp de lungime capacitate + 1, plin de 0.
  • Pentru fiecare obiect, parcurge capacitățile **de la capacitate în jos până la greutatea obiectului**.
  • Actualizează dp[c] = max(dp[c], dp[c - g] + v). Trebuie să apară: 9, 220, 3.

Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Ce urmează în curs

  1. Primii pași, tablouri, two pointers și sliding window Lecțiile 3–40 · 38 de lecții certificat
  2. Hash map, stive, cozi și liste înlănțuite Lecțiile 41–65 · 25 de lecții certificat
  3. Recursivitate, backtracking, sortare și căutare binară Lecțiile 66–95 · 30 de lecții certificat
  4. Arbori, grafuri și heap Lecțiile 96–125 · 30 de lecții certificat
  5. Programare dinamică și interviuri simulate Lecțiile 126–150 · 25 de lecții certificat

Ce primești

  • Lecții interactive în limba română, cu cod scris și rulat direct în browser
  • Exerciții verificate automat, cu feedback pe loc
  • Certificat la finalul fiecărui modul, verificabil online
  • Acces pe viață, în ritmul tău, fără abonament

4,9 din 5 · 128 de recenzii Google

Profesorii si colegii foarte prietenosi,modul in care se preda simplu si usor de inteles cu exemple practice incat oricine poate prinde usor.
Alex Cristian
Foarte profi si utile cursurile. Practica aplicata si explicata de traineri inarmati cu rabdare si cunostine solide.
Iulian Pahom
Cursuri foarte utile si profesori foarte pregatiti. Recomand cu toata increderea.
Catalina Ioana Dan
Toate recenziile pe Google