Problema Rucsacului în C++

Enunț

Avem n obiecte, fiecare cu greutate w[i] și valoare v[i]. Trebuie să selectăm obiecte pentru a maximiza valoarea totală, fără a depăși capacitatea W a rucsacului.

Varianta 0/1 (Programare Dinamică)

Fiecare obiect poate fi luat complet sau deloc.

Copiază
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int rucsac01(int W, vector<int>& greutate, vector<int>& valoare) {
7    int n = greutate.size();
8    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
9    
10    for (int i = 1; i <= n; i++) {
11        for (int w = 0; w <= W; w++) {
12            // Nu luăm obiectul i
13            dp[i][w] = dp[i-1][w];
14            
15            // Luăm obiectul i (dacă încape)
16            if (greutate[i-1] <= w) {
17                dp[i][w] = max(dp[i][w], 
18                    dp[i-1][w - greutate[i-1]] + valoare[i-1]);
19            }
20        }
21    }
22    
23    return dp[n][W];
24}
25
26int main() {
27    int n, W;
28    cin >> n >> W;
29    
30    vector<int> greutate(n), valoare(n);
31    for (int i = 0; i < n; i++) {
32        cin >> greutate[i] >> valoare[i];
33    }
34    
35    cout << rucsac01(W, greutate, valoare) << endl;
36    return 0;
37}

Optimizare Spațiu O(W)

Copiază
1int rucsac01_optimizat(int W, vector<int>& g, vector<int>& v) {
2    int n = g.size();
3    vector<int> dp(W + 1, 0);
4    
5    for (int i = 0; i < n; i++) {
6        // Parcurgem de la W la g[i] pentru a nu folosi valoarea actualizată
7        for (int w = W; w >= g[i]; w--) {
8            dp[w] = max(dp[w], dp[w - g[i]] + v[i]);
9        }
10    }
11    
12    return dp[W];
13}

Varianta Fracționară (Greedy)

Putem lua fracțiuni din obiecte.

Copiază
1#include <algorithm>
2
3struct Obiect {
4    int greutate, valoare;
5    double raport() const { return (double)valoare / greutate; }
6};
7
8double rucsacFractionar(int W, vector<Obiect>& obiecte) {
9    // Sortăm după raportul valoare/greutate descrescător
10    sort(obiecte.begin(), obiecte.end(), 
11        [](const Obiect& a, const Obiect& b) {
12            return a.raport() > b.raport();
13        });
14    
15    double valoareTotala = 0;
16    int capacitateRamasa = W;
17    
18    for (const auto& obj : obiecte) {
19        if (capacitateRamasa >= obj.greutate) {
20            // Luăm obiectul complet
21            valoareTotala += obj.valoare;
22            capacitateRamasa -= obj.greutate;
23        } else {
24            // Luăm fracțiune
25            valoareTotala += obj.raport() * capacitateRamasa;
26            break;
27        }
28    }
29    
30    return valoareTotala;
31}

Complexitate