Rucsacul 0/1: alegere și reconstruire în C++

Fiecare obiect are o greutate și o valoare. Alegem obiecte cu greutatea totală cel mult C și vrem valoarea totală maximă. Fiecare obiect poate fi luat o singură dată: acesta este sensul lui 0/1. Nu avem voie să tăiem obiectele în fracții.

Sortarea după raportul valoare/greutate rezolvă o altă variantă, cu fracții. Aici trebuie să comparăm posibilitatea de a lua sau de a omite fiecare obiect. În plus față de valoarea maximă, vom afișa indicii unei selecții optime.

Cum funcționează

Definim d[i][c] ca valoarea maximă obținută folosind primele i obiecte și o capacitate de cel mult c. Cuvintele „cel mult” sunt esențiale: nu cerem să umplem exact rucsacul. Fără obiecte, valoarea este zero pentru orice capacitate, deci linia d[0][c] este zero.

Pentru obiectul i avem două opțiuni. Dacă îl omitem, păstrăm d[i-1][c]. Dacă w[i]<=c și îl luăm, obținem d[i-1][c-w[i]]+value[i]. Alegem maximul. Ambele opțiuni folosesc linia i-1, deci obiectul curent nu poate apărea de două ori.

La reconstruire pornim de la (n,C). Dacă d[i][c] este egal cu d[i-1][c], există o soluție optimă care omite obiectul i, iar implementarea o preferă. Altfel, obiectul i trebuie luat: îi memorăm indicele și scădem greutatea din capacitate. În ambele cazuri scădem i. Indicii rezultați în ordine descrescătoare sunt afișați invers.

Intrarea conține n și C, apoi câte o pereche greutate-valoare pentru fiecare obiect. Presupunem 1<=n<=50, 0<=C<=500, 1<=w[i]<=500 și 0<=value[i]<=1000. Ieșirea conține valoarea maximă, apoi numărul obiectelor alese, apoi indicii lor de la unu. Dacă nu alegem nimic, ultima linie este vidă. Valoarea totală este cel mult 50000, deci încape în int.

Tabloul d are capacitate 51x501, dar numai liniile 0..n și coloanele 0..C sunt logice. Obiectele folosesc indicii 1..n, iar lista chosen folosește 0..count-1. Varianta std::vector alocă dimensiunile corespunzătoare și păstrează exact aceste convenții. Apelul std::max compară două valori și vine din antetul algorithm.

Există și o optimizare la o singură linie, dacă ne interesează doar valoarea. Atunci capacitatea trebuie parcursă descrescător pentru fiecare obiect. Parcurgerea crescătoare poate reciti o stare care include deja obiectul curent și transformă problema într-una cu reutilizare. Păstrăm aici două dimensiuni pentru ca alegerea și reconstruirea să rămână ușor de urmărit.

Exemplu urmărit pas cu pas

Avem obiectele (2,3), (3,4), (4,5), unde fiecare pereche este (greutate,valoare), și C=5:

i / capacitate   0  1  2  3  4  5
0                0  0  0  0  0  0
1                0  0  3  3  3  3
2                0  0  3  4  4  7
3                0  0  3  4  5  7

La (2,5), luarea obiectului doi produce d[1][2]+4=7. La (3,5), obiectul trei ar produce numai d[2][1]+5=5, deci îl omitem. Reconstruim indicii 2 și 1, apoi afișăm 1 2. Greutatea este 2+3=5, iar valoarea 3+4=7.

Implementare C++17

Varianta cu tablou clasic:

#include <algorithm>
#include <iostream>
int main() {
    int n, capacity;
    std::cin >> n >> capacity;
    int w[51], value[51], d[51][501] = {}, chosen[51];
    for (int i = 1; i <= n; ++i)
        std::cin >> w[i] >> value[i];
    for (int i = 1; i <= n; ++i)
        for (int c = 0; c <= capacity; ++c) {
            d[i][c] = d[i - 1][c];
            if (w[i] <= c)
                d[i][c] = std::max(d[i][c], d[i - 1][c - w[i]] + value[i]);
        }
    std::cout << d[n][capacity] << '\n';
    int c = capacity, count = 0;
    for (int i = n; i >= 1; --i)
        if (d[i][c] != d[i - 1][c]) {
            chosen[count++] = i;
            c -= w[i];
        }
    std::cout << count << '\n';
    for (int i = count - 1; i >= 0; --i)
        std::cout << chosen[i] << (i == 0 ? '\n' : ' ');
    if (count == 0)
        std::cout << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n, capacity;
    std::cin >> n >> capacity;
    std::vector<int> w(n + 1), value(n + 1), chosen(n + 1);
    std::vector<std::vector<int>> d(n + 1, std::vector<int>(capacity + 1, 0));
    for (int i = 1; i <= n; ++i)
        std::cin >> w[i] >> value[i];
    for (int i = 1; i <= n; ++i)
        for (int c = 0; c <= capacity; ++c) {
            d[i][c] = d[i - 1][c];
            if (w[i] <= c)
                d[i][c] = std::max(d[i][c], d[i - 1][c - w[i]] + value[i]);
        }
    std::cout << d[n][capacity] << '\n';
    int c = capacity, count = 0;
    for (int i = n; i >= 1; --i)
        if (d[i][c] != d[i - 1][c]) {
            chosen[count++] = i;
            c -= w[i];
        }
    std::cout << count << '\n';
    for (int i = count - 1; i >= 0; --i)
        std::cout << chosen[i] << (i == 0 ? '\n' : ' ');
    if (count == 0)
        std::cout << '\n';
}

De ce funcționează și cât costă

Orice selecție din primele i obiecte fie îl conține pe i, fie nu. În primul caz, eliminarea lui lasă o selecție din primele i-1 obiecte cu capacitate redusă. Dacă partea rămasă nu este optimă, o putem îmbunătăți. Maximizarea celor două cazuri acoperă toate selecțiile valide.

Timpul este O(nC), memoria tabelului este O(nC), iar reconstruirea are O(n) pași. Complexitatea depinde de valoarea numerică a capacității, nu doar de numărul cifrelor ei; pentru capacități foarte mari această metodă poate deveni nepotrivită.

Greșeli frecvente

Nu folosi linia i în tranziția care ia obiectul. Nu confunda capacitatea maximă cu greutatea exactă. Dacă ceri greutate exactă, unele stări trebuie marcate imposibile, nu inițializate toate cu zero.

Exersează

Ai un singur obiect cu greutate 2 și valoare 3, iar capacitatea este 4. Care este răspunsul 0/1 și ce răspuns greșit ar produce reutilizarea obiectului?

Rezolvare explicată: În rucsacul 0/1 obții valoarea 3, folosind obiectul o singură dată. Reutilizarea ar produce 6, deși intrarea conține un singur obiect. Acesta este un test mic care detectează sensul greșit al buclei în implementarea cu o singură linie.

Probleme de practică

Rezolvă cele trei probleme în ordinea de mai jos. Deschide fiecare problemă, scrie soluția și verific-o folosind testele locale din pagină. Respectă formatul de intrare, limitele și ieșirea cerută; acestea pot diferi de programul din lecție. Trimiterea pentru punctaj necesită autentificare și un evaluator activ.

1. Rucsacul cu obiecte. Alege fiecare obiect cel mult o dată și maximizează valoarea fără depășirea capacității. Problema cere valoarea optimă, fără lista obiectelor; adaptează tablourile la limitele enunțului.

2. Câte totaluri diferite putem forma?. Înlocuiește valoarea maximă cu informația dacă o sumă este realizabilă. Numără sumele distincte, inclusiv zero, nu selecțiile care le produc.

3. Împarte greutățile echilibrat. Extensie de modelare: folosește sumele realizabile pentru a forma două grupe cât mai apropiate. Fiecare obiect aparține exact uneia dintre grupe.

Continuă să înveți

Înapoi la programarea dinamică. Recapitulează tablourile și recursivitatea.

Întrebări frecvente

De ce nu aleg doar cel mai valoros obiect?

El poate consuma capacitatea care ar permite mai multe obiecte cu valoare totală mai mare. Trebuie comparate selecțiile posibile în limita greutății.

Pot exista mai multe selecții optime?

Da. Codul omite obiectul curent la egalitate și afișează o selecție optimă, fără să promită o regulă lexicografică generală.

Obiectele cu greutate egală sunt duplicate?

Nu neapărat. Fiecare linie reprezintă un obiect distinct, cu propriul indice, care poate fi ales o dată.

De ce păstrăm întregul tabel?

El permite să comparăm soluția curentă cu starea care omite ultimul obiect și să reconstruim alegerea. Compresia memoriei necesită atenție suplimentară pentru traseu.

Ce se întâmplă la capacitate zero?

Greutățile sunt strict pozitive, deci nu alegem niciun obiect. Valoarea maximă și numărul obiectelor sunt zero.