Greedy: Rucsacul fracționar

Ai un rucsac cu capacitatea W. Ai N obiecte, fiecare cu greutatea g[i] și valoarea v[i]. Poți tăia obiectele - iei oricât de puțin sau mult din fiecare. Care e valoarea maximă care încape?

Atenție: aceasta e versiunea fracționară (poți tăia). Versiunea 0/1 (iei tot sau deloc) NU se rezolvă cu greedy - vezi la final.

Ideea greedy

Sortează obiectele descrescător după raportul valoare/greutate (v[i] / g[i]). Apoi ia cât mai mult din fiecare obiect, în ordine.

sortează descrescător după v[i] / g[i]
total_val = 0
W_ramas = W
pentru fiecare obiect (g, v):
    dacă g ≤ W_ramas:
        ia tot obiectul: total_val += v, W_ramas -= g
    altfel:
        ia o fracțiune: total_val += v · (W_ramas / g), W_ramas = 0
        STOP

Intuiția

Raportul v/g = „cât valoare îmi dă fiecare unitate de greutate”. Cea mai bună „rentabilitate per kilogram” → o iau prima.

Dacă obiectul nu încape întreg, iau cât pot - pentru că fiecare gram din el e mai valoros decât oricare gram din restul.

De ce funcționează (exchange argument)

Teoremă: alegerea greedy duce la valoarea maximă posibilă.

Dem (schiță): Fie OPT o soluție optimă care diferă de greedy. Înseamnă că OPT ia mai puțin dintr-un obiect cu raport mare și mai mult dintr-unul cu raport mic. Putem schimba un gram dintre cele două: scoatem 1 gram din cel cu raport mic și înlocuim cu 1 gram din cel cu raport mare. Valoarea totală crește (sau rămâne) - contradicție cu optimalitatea OPT.

Deci OPT = greedy. ∎

Pas cu pas

Capacitate W = 50. Obiecte:

Obiect  Greutate  Valoare  Raport (v/g)
A       10        60       6.0
B       20        100      5.0
C       30        120      4.0

Sortare după raport (deja sortat):

Total: 240 ✓.

(Verificare: dacă luam B + C întregi: g = 50 ≤ 50, v = 220. Mai puțin decât 240 - confirmă că greedy e mai bun.)

Cod

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int NMAX = 100005;

struct Obiect {
    int g, v;
};

Obiect ob[NMAX];
int n;
double W;

bool cmpRaport(Obiect a, Obiect b) {
    // descrescător după v / g, fără diviziune: a.v * b.g > b.v * a.g
    return (long long)a.v * b.g > (long long)b.v * a.g;
}

int main() {
    fin >> n >> W;
    for (int i = 1; i <= n; i++) {
        fin >> ob[i].g >> ob[i].v;
    }

    sort(ob + 1, ob + n + 1, cmpRaport);

    double total = 0;
    for (int i = 1; i <= n; i++) {
        if (ob[i].g <= W) {
            total = total + ob[i].v;
            W = W - ob[i].g;
        } else {
            total = total + ob[i].v * (W / ob[i].g);
            break;
        }
    }
    fout << total;
    return 0;
}

Complexitate: O(N log N) - sortarea domină.

Atenție la precizie

Folosim double pentru raport și pentru rezultat. Dacă enunțul cere răspunsul cu un anumit număr de zecimale, folosește setprecision:

#include <iomanip>
fout << fixed << setprecision(2) << total;

Sau, dacă enunțul garantează că răspunsul e întreg (greutățile și valorile sunt mici), poți lucra cu fracții (numerator/denumitor) sau înmulți totul cu un denominator comun.

Variantă: comparator fără diviziune (pentru precizie)

Pentru a evita probleme de virgulă mobilă la sortare, comparăm raporturile prin înmulțire încrucișată:

// (a.v / a.g) > (b.v / b.g)
// echivalent cu: a.v * b.g > b.v * a.g
bool cmp(Obiect a, Obiect b) {
    return (long long)a.v * b.g > (long long)b.v * a.g;
}
sort(ob + 1, ob + n + 1, cmp);

Atenție la overflow: dacă v, g ≤ 10⁵, atunci v * g ≤ 10¹⁰ → folosește long long.

Rucsacul 0/1 (NU greedy!)

Aceleași date, dar NU poți tăia - iei tot obiectul sau nu îl iei deloc.

Greedy după raport eșuează. Contraexemplu:

W = 4
Obiecte:
A: g=1, v=1   (raport 1.0)
B: g=2, v=4   (raport 2.0)
C: g=3, v=5   (raport 1.67)

Greedy după raport: B (g=2, v=4), apoi A (g=1, v=1) → total greutate 3, val 5.
Restul de greutate (1) nu permite C. Total: 5.

Optim 0/1: B + C → g=5 > 4, nu încape. A + C → g=4 ≤ 4, val=6. Sau B + A → 5.

Hm, în acest caz simplu greedy ar putea da 5, optim e 6. Diferență mică.

Exemplu mai grav:

W = 50
A: g=10, v=60 (raport 6.0)
B: g=20, v=100 (raport 5.0)
C: g=30, v=120 (raport 4.0)

Greedy 0/1: A + B → g=30, v=160. Restul 20 nu permite C (g=30). Total: 160.
Optim: B + C → g=50, v=220. Greedy ratează 60 unități.

Pentru rucsac 0/1 → DP

const int WMAX = 100005;
int dp[WMAX]; // dp[w] = valoare maximă cu greutate ≤ w

for (int i = 1; i <= n; i++) {
    for (int w = W; w >= ob[i].g; w--) {  // ATENȚIE: descrescător
        int candidat = dp[w - ob[i].g] + ob[i].v;
        if (candidat > dp[w]) {
            dp[w] = candidat;
        }
    }
}

fout << dp[W];

Complexitate O(N · W). Funcționează când W ≤ 10⁵ (memoria devine limitarea).

Greșeli frecvente

1. Folosirea greedy pentru rucsac 0/1

Cea mai des întâlnită eroare la începători. 0/1 → DP, nu greedy.

2. Sortare crescătoare după raport

Trebuie descrescător - vrei rentabilitatea cea mai bună întâi.

3. Uitarea cazului „obiect parțial”

if (ob[i].g <= W) {
    total += ob[i].v;
    W -= ob[i].g;
}
// FĂRĂ else → ratez ultimul obiect parțial

Trebuie else { fracțiune; break; }.

4. Probleme de precizie cu double

Pentru ieșire, folosește setprecision. Pentru sortare, înmulțire încrucișată cu long long.

5. Overflow la valori mari

Dacă v · g ≤ 10¹⁸, folosește long long. Altfel, posibil overflow chiar și la sortare.

Ce să reții

• Rucsac fracționar (poți tăia) → greedy după v/g descrescător, funcționează.
• Rucsac 0/1 (tot sau nimic) → DP, NU greedy.
• Comparator fără virgulă mobilă: a.v * b.g > b.v * a.g (overflow cu long long).
• Demonstrație: exchange argument - un gram cu raport mare e mai bun decât unul cu raport mic.
• Atenție la output: folosește setprecision pentru zecimale.
• Greedy fracționar = upper bound pentru rucsac 0/1, util în optimizări.

Probleme

pbinfoRucsac→