Podczas pisania stron internetowych, a szczególnie w przypadku pisania sklepu internetowego prędzej czy później trafisz na problem Plecakowy. Czyli jak zoptymalizować pakowanie paczek do jakiegoś pojemnika. Wyobraźmy sobie sytuacje, że tworzymy list przewozowy dla kuriera. Klient w sklepie zamówił towary, które mają różną wagę. Naszym zadaniem jest tak spakować produkty by klient zapłacił jak najmniej za przesyłkę.
Problem plecakowy(ang. discrete knapsack problem) jest jednym z najczęściej występujących problemów optymalizacyjnych, przy którym należy wykorzystać algorytmy zachłanne.
Problem plecakowy czyli jak zoptymalizować pakowanie:
Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.
Jak to zrobić?
Najlepszym rozwiązaniem jest posortowanie paczek po wadze i pakowanie ich do plecaka od najcięzszej do najlżejszej. W przypadku braku miejsca, bierzemy nowy plecak.
Rozwiązanie problemu w PHP – kod obiektowy
[…]