Double greedy approximation algorithm of containers packing

Problemem opisywanym w pracy jest spakowanie zbioru paczek o zadanych pojemnościach do minimalnej liczby aut o jednakowej pojemności. Przedstawiono w niej algorytm siłowy oraz dwa algorytmy aproksymacyjne (FFA oraz FFDA). Zaprezentowano wiele ciekawych przykładów ilustrujących działanie tych algorytmów. Szczególnie ważnym elementem zawartym w pracy są przykłady anomalii pokazujące nieoczekiwane własności algorytmu FFDA, polegające na otrzymaniu mniejszej liczby aut pomimo zwiększenia zbioru paczek.

The problem described in this work is to pack a set of packages with the given capacities to a minimum number of cars of the same capacity. It shows brute force algorithm and two approximation algorithms (FFA and FFDA). It presents many interesting examples to illustrate the operation of these algorithms. A particularly important element included in the job are examples of anomalies showing unexpected properties of the algorithm FFDA, consisting in receiving fewer cars despite the increase in collection packages.