Acest proiect implementează și compară patru algoritmi pentru problema Bin Packing, măsurând performanța și calitatea soluțiilor pe un set divers de teste.
-
algoritm.cpp- Implementarea principală a celor patru algoritmi:- Next Fit (NF): O(N) - cel mai simplu algoritm, pune obiectul în cosul curent sau deschide unul nou
- First Fit (FF): O(N²) - caută primul cos disponibil în care încape obiectul
- Best Fit Decreasing (BFD): O(N log N) - sortează obiectele descrescător și folosește un arbore binar echilibrat pentru a găsi cel mai bun cos
- Brute Force: O(2^N) - găsește soluția optimă prin backtracking (doar pentru N ≤ 50)
-
generator.py- Script Python care generează automat toate testele din folderulinput/. Creează 30 de teste organizate în 6 categorii strategice. -
Makefile- Fișier de build pentru compilarea programului C++ -
rezultate.csv- Fișier CSV generat automat care conține rezultatele tuturor testelor (nume test, N, capacitate, algoritm, număr coșuri, timp execuție)
Testele sunt create automat cu generator.py și sunt organizate în 6 grupe strategice:
- Scop: Măsurarea timpului de execuție pe input-uri de dimensiuni crescătoare
- Caracteristici: N crește de la 5 la 50, obiecte aleatoare între 1 și 100
- Relevanță: Demonstrează complexitatea temporală a fiecărui algoritm
- Scop: Verificarea eficienței umplerii golurilor
- Caracteristici: N=1000, obiecte foarte mici (1-20)
- Relevanță: Testează capacitatea algoritmilor de a optimiza spațiul rămas în coșuri
- Scop: Verificarea comportamentului pe obiecte mari (>50% din capacitate)
- Caracteristici: N=1000, obiecte între 51 și 100
- Relevanță: Toți algoritmii ar trebui să dea rezultate similare (fiecare obiect într-un cos separat)
- Scop: Demonstrarea limitărilor algoritmului Next Fit
- Caracteristici: N=1000, pattern alternat: obiect mic (20) urmat de obiect mare (80)
- Relevanță: Next Fit va deschide un cos nou la fiecare obiect mare, în timp ce First Fit le va împerechea eficient
- Scop: Demonstrarea importanței sortării pentru algoritmii greedy
- Caracteristici: N=999, pattern de tip 60-20-20 amestecat aleator
- Relevanță: Arată de ce BFD (sortat descrescător) este superior lui FF (nesortat)
- Test 26 (Edge_Full): Toate obiectele egale cu capacitatea (500 obiecte de 100)
- Test 27 (Edge_Min): Toate obiectele au mărimea 1 (500 obiecte de 1)
- Test 28 (Edge_Perfect): Suma obiectelor este exact K × Capacitate (250 perechi de 50)
- Test 29 (Edge_SmallCap): Capacitate mică (10) cu obiecte variate
- Test 30 (Edge_Massive): Scală masivă (100.000 obiecte)
Rulează scriptul Python pentru a genera toate testele în folderul input/:
python3 generator.pyAcest script va:
- Șterge folderul
input/vechi (dacă există) - Crea un nou folder
input/ - Genera 30 de fișiere de test numerotate de la
test_01_Random.txtlatest_30_Edge_Massive.txt
Folosește Makefile pentru a compila programul C++:
makeAceasta va compila algoritm.cpp într-un executabil numit algoritm.
Rulează executabilul pentru a procesa toate testele:
make runProgramul va:
- Parcurge toate fișierele
.txtdin folderulinput/ - Rula fiecare algoritm pe fiecare test
- Măsura timpul de execuție pentru fiecare algoritm
- Scrie rezultatele în
rezultate.csv
Notă: Algoritmul Brute Force rulează doar pentru teste cu N ≤ 50 din motive de performanță.
Pentru a șterge fișierele compilate și rezultatele:
make cleanAceasta va șterge executabilul algoritm și fișierul rezultate.csv.
- C++: Compilator C++17 (clang++ sau g++)
- Python 3: Pentru
generator.pyșigrafice.py - Python Packages (pentru grafice):
- pandas
- matplotlib
- seaborn
Pentru a instala dependențele Python:
pip install pandas matplotlib seaborn- Next Fit: Cel mai rapid, dar cel mai puțin eficient în termeni de număr coșuri
- First Fit: Echilibru între viteză și calitate
- BFD (Best Fit Decreasing): Cel mai bun algoritm greedy, aproape de optim în majoritatea cazurilor
- Brute Force: Soluție optimă, dar doar pentru input-uri mici (N ≤ 50)