Rucsac nelimitat: reutilizarea obiectelor în C++

În rucsacul nelimitat, fiecare tip de obiect poate fi ales de oricâte ori, atât timp cât greutatea totală nu depășește capacitatea. Dacă avem un obiect de greutate 3 și valoare 5, la capacitatea 6 putem lua două exemplare, obținând valoarea 10.

Ce reprezintă best[c]

Folosim programare dinamică: best[c] este valoarea maximă pentru o greutate totală cel mult c, folosind tipurile deja procesate. Nu cerem umplerea exactă a capacității. De aceea toate stările pot începe cu zero, alegerea de a nu lua nimic.

Citim 1≤n≤100 și capacitatea C între 0 și 10000. Urmează n perechi greutate, valoare, cu 1≤greutate≤10000 și 0≤valoare≤10^6. Greutățile sunt strict pozitive. Un obiect cu greutate zero și valoare pozitivă ar permite valoare nelimitată și nu este acceptat.

Refolosirea este intenționată

Pentru un tip de greutate g și valoare v, comparăm răspunsul actual cu best[c-g]+v. Parcurgem capacitățile crescător. Astfel best[c-g] poate include deja același tip din etapa curentă, ceea ce permite adăugarea încă unui exemplar.

Aceasta este diferența esențială față de rucsacul 0/1, în care fiecare obiect poate fi ales o singură dată și capacitățile se parcurg descrescător. Nu schimba direcția doar pentru că rezultatul coincide pe un exemplu mic.

Un obiect de greutate 3 și valoare 5 poate fi luat de două ori la capacitatea 6. Valorile optime la capacitățile 0,3,6 sunt 0,5,10.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n,c; cin >> n >> c;
    int greutate[100]; long long valoare[100],best[10001]={};
    for(int i=0;i<n;++i) cin >> greutate[i] >> valoare[i];
    for(int i=0;i<n;++i)
        for(int capacitate=greutate[i];capacitate<=c;++capacitate)
            best[capacitate]=max(best[capacitate],best[capacitate-greutate[i]]+valoare[i]);
    cout << best[c] << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n,c; cin >> n >> c;
    vector<int> greutate(n); vector<long long> valoare(n),best(c+1);
    for(int i=0;i<n;++i) cin >> greutate[i] >> valoare[i];
    for(int i=0;i<n;++i)
        for(int capacitate=greutate[i];capacitate<=c;++capacitate)
            best[capacitate]=max(best[capacitate],best[capacitate-greutate[i]]+valoare[i]);
    cout << best[c] << '\n';
}

Urmărește două exemplare identice

Pentru greutate 3 și valoare 5, la capacitatea 3 obținem best[3]=5. Când ajungem la 6, folosim acea stare și obținem best[6]=best[3]+5=10. O parcurgere descrescătoare nu ar vedea best[3] actualizat și ar permite doar un exemplar.

Cu tipurile (3,5) și (4,6), la capacitatea 7 alegem câte unul și obținem 11. La capacitatea 2 nu încape niciun obiect, deci rezultatul este 0. Acest ultim caz este valid deoarece umplerea exactă nu este cerută.

Numărul maxim de exemplare este C, deoarece fiecare greutate este cel puțin 1. Valoarea totală este astfel cel mult 10^10 în limitele date, motiv pentru folosirea lui long long. Indicii obiectelor sunt 0..n-1, iar stările capacității 0..C.

Timpul este O(n·(C+1)), memoria O(n+C). Tablourile clasice rezervă 100 de tipuri și 10001 de stări; varianta vector alocă dimensiunile logice necesare.

Exersează

Testează un singur tip (3,5) la capacitatea 6, apoi cele două tipuri de mai sus la capacitatea 7. Răspunsurile sunt 10 și 11. Verifică C=0 și cazul în care toate greutățile depășesc capacitatea. Explică de ce raportul valoare/greutate nu oferă singur o soluție generală pentru obiecte indivizibile.

Continuă cu rucsacul 0/1, problemele cu monede și programarea dinamică.

Întrebări frecvente

Ce înseamnă rucsac nelimitat?

Fiecare tip de obiect poate fi ales de oricâte ori, respectând capacitatea totală. Se urmărește valoarea maximă, iar numărul copiilor unui tip nu este limitat la unu.

De ce actualizarea crescătoare permite repetarea unui obiect?

La capacitatea c, starea pentru c-w poate conține deja obiectul curent. Adăugarea lui încă o dată construiește o soluție cu mai multe exemplare, ceea ce este permis aici.

Trebuie umplută exact capacitatea în această lecție?

Nu. Greutatea totală trebuie să fie cel mult capacitatea. De aceea selecția goală este permisă și stările pot porni de la valoarea zero.