Rucsac fracționat folosind C++

Introducere în programarea dinamică

Programarea dinamică reprezintă o tehnică eficientă de rezolvare a problemelor, care implică descompunerea acestora în subprobleme mai simple, ce se suprapun parțial. Această metodă facilitează abordarea problemelor complexe prin transformarea lor în elemente mai mici și ușor de gestionat.

Conceptul de rucsac fracționat

Problema rucsacului fracționat constituie un exemplu clasic ce demonstrează aplicabilitatea programării dinamice. În cadrul acestei probleme, ni se prezintă un set de obiecte, fiecare având o anumită greutate și o valoare specifică, alături de un rucsac cu o capacitate limitată. Scopul este de a optimiza selecția obiectelor pentru a umple rucsacul, astfel încât valoarea totală a acestora să fie maximizată, fără a depăși capacitatea rucsacului.

Algoritmul folosit în problema rucsacului fracționat

Algoritmul pentru rucsacul fracționat se bazează pe principiile programării dinamice și urmează următorii pași:

– Inițializarea: Se creează o tabelă (matrice) ‘dp’ cu dimensiunile m x n, unde ‘m’ reprezintă numărul de obiecte, iar ‘n’ reprezintă capacitatea rucsacului. Fiecare element al tabelei ‘dp’ va stoca valoarea maximă posibilă pentru o subproblemă specifică.
– Populează matricea: Se parcurge fiecare obiect ‘i’ și fiecare capacitate ‘j’ a rucsacului, de la 0 la ‘n’. Pentru fiecare combinație, se calculează valoarea maximă ce poate fi obținută umplând rucsacul, folosind principiile programării dinamice:
– Dacă greutatea obiectului curent ‘i’ este mai mare decât capacitatea curentă ‘j’, atunci valoarea maximă rămâne aceeași cu cea obținută fără a include obiectul ‘i’.
– Altfel, valoarea maximă devine cea mai mare dintre valoarea deja calculată sau valoarea obținută prin includerea obiectului ‘i’ plus valoarea maximă obținută pentru capacitatea (j – greutatea obiectului ‘i’).
– Determinarea soluției: După popularea matricei ‘dp’, obiectele ce alcătuiesc soluția optimă sunt determinate prin parcurgerea matricei în sens invers, de la sfârșit către început.

Implementarea în C++ a algoritmului

Codul C++ următor implementează algoritmul rucsacului fracționat pentru a determina profitul maxim ce poate fi obținut prin umplerea rucsacului cu obiecte date:

#include <iostream>
#include <vector>

using namespace std;

int main() {
  // Numărul total de obiecte
  int m;
  // Capacitatea maximă a rucsacului
  int n;
  // Vector pentru stocarea greutăților obiectelor
  vector<int> greutati;
  // Vector pentru stocarea valorilor obiectelor
  vector<int> valori;

  // Citirea datelor de intrare
  cin >> m >> n;
  greutati.resize(m);
  valori.resize(m);
  for (int i = 0; i < m; i++) {
    cin >> greutati[i] >> valori[i];
  }

  // Crearea matricei pentru programarea dinamică
  vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

  // Umplerea matricei dp
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (greutati[i - 1] <= j) {
        dp[i][j] = max(dp[i - 1][j], valori[i - 1] + dp[i - 1][j - greutati[i - 1]]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  // Afișarea profitului maxim
  cout << dp[m][n] << endl;

  return 0;
}

Evaluarea complexității algoritmului

Complexitatea temporală a algoritmului rucsacului fracționat este de O(mn), unde ‘m’ este numărul de obiecte, iar ‘n’ este capacitatea totală a rucsacului. Complexitatea spațială este, de asemenea, O(mn), dată de dimensiunea matricei ‘dp’ necesară pentru calcul.

Concluzii despre problema rucsacului fracționat

Problema rucsacului fracționat reprezintă un exemplu excelent ce demonstrează eficacitatea programării dinamice. Algoritmul prezentat utilizează această tehnică pentru a identifica soluția optimă într-un mod eficient din punct de vedere al timpului și spațiului. Abordarea programării dinamice se dovedește utilă în multe alte probleme de optimizare, oferind o metodă solidă pentru rezolvarea problemelor complexe prin descompunerea lor în unități mai mici.

Întrebări frecvente legate de rucsacul fracționat

1. Care este diferența esențială între problema rucsacului fracționat și cea a rucsacului 0-1?
– În problema rucsacului fracționat, este permis să luăm porțiuni din fiecare obiect, în timp ce în problema rucsacului 0-1, trebuie să alegem fie obiectul integral, fie deloc.

2. Care este complexitatea temporală a algoritmului de rezolvare a problemei rucsacului fracționat?
– Complexitatea temporală a algoritmului este de O(mn), unde ‘m’ reprezintă numărul de obiecte, iar ‘n’ este capacitatea rucsacului.

3. Cum putem identifica obiectele incluse în soluția optimă după calcularea matricei dp?
– Obiectele selectate sunt determinate prin parcurgerea matricei ‘dp’ în ordine inversă, de la ultimul element către primul, urmărind deciziile luate pentru a maximiza valoarea.

4. În ce situații este algoritmul rucsacului fracționat deosebit de util?
– Algoritmul rucsacului fracționat este aplicabil atunci când putem sau trebuie să utilizăm părți din obiecte.

5. Care sunt alte scenarii în care programarea dinamică își găsește utilitatea?
– Programarea dinamică este o tehnică versatilă, utilizată în numeroase probleme de optimizare, cum ar fi determinarea celei mai lungi subsecvențe comune, calculul distanței editare și problema tăierii tijelor.

6. De ce este crucială descompunerea problemelor în subprobleme în contextul programării dinamice?
– Descompunerea în subprobleme ne permite să abordăm probleme complexe, transformându-le în componente mai simple și ușor de gestionat.

7. Ce avantaje oferă folosirea matricei ‘dp’ în implementarea algoritmului rucsacului fracționat?
– Matricea ‘dp’ stochează soluțiile optime pentru subprobleme, eliminând necesitatea recalculării lor repetate, ceea ce duce la creșterea eficienței algoritmului.

8. Cum am putea optimiza algoritmul rucsacului fracționat?
– O metodă de optimizare ar fi sortarea obiectelor în funcție de raportul valoare/greutate și aplicarea unei abordări de tip greedy, selectând obiectele cu cel mai mare raport valoare/greutate până când rucsacul este plin.