© Jakub Wroblewski     (jesli nie zaznaczono inaczej)

Zadania optymalizacyjne

Stierlitz wolnym krokiem wszedł do kawiarni Elefant...

Zbiór zadań zahaczających o takie tematy, jak algorytmy optymalizacji dyskretnej (wychładzanie, algorytmy ewolucyjne, heurystyki zachłanne) dla problemów NP-trudnych. Swego czasu chadzały na egzaminach.


Problem pakowania (bin packing)

Danych jest n obiektów, każdy o pewnym rozmiarze wi. Dana jest też dowolnie duża liczba skrzyń, z których każda ma ustaloną pojemność W. Zadanie: umieścić wszystkie n obiektów w skrzyniach w ten sposób, by nie przekroczyć ich pojemności (tzn. by suma wielkości wi obiektów przypisanych jednej skrzyni była nie większa, niż W), przy czym należy w tym celu użyć możliwie małej liczby skrzyń.

- - - - - - - -