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
<?php class Plecak { private $pojemnosc; public $pozostalo; private $paczki; public function __construct($p) { $this->pojemnosc = $p; $this->pozostalo = $p; } public function dodajPaczke(Paczka $paczka) { $this->paczki[] = $paczka; $this->pozostalo -= $paczka->zwrocWage(); } public function ustawPojemnosc($pojemnosc){ $this->pojemnosc = $pojemnosc;} public function zwrocPojemnosc(){ return $this->pojemnosc; } public function zobaczPaczki() { if($this->pojemnosc == $this->pozostalo) { echo '<br>plecak jest pusty<br>'; } else { echo 'W plecaku o pojemnosci '.$this->pojemnosc.' sa: <br>'; $i = 0; foreach($this->paczki as $p) { $i++; echo 'paczka nr '.$i.' - '.$p->zwrocWage().'kg <br>'; } echo '<br>Zostało miejsca: '.$this->pozostalo.'<br>-----<br>'; } } } class Paczka { private $waga; public function __construct($w) { $this->waga = $w; } public function ustawWage($waga){ $this->waga = $waga;} public function zwrocWage(){ return $this->waga; } } $maksymalnaWagaPaczki = 8; $pojemnoscPlecaka = 20; $liczbaPaczek = 10; $liczbaPlecakow = 3; $paczki = array(); for($i = 0 ; $i < 10; ++$i) { $waga = 1 + ceil(rand()%$maksymalnaWagaPaczki) ; $paczki[] = new Paczka($waga); } $plecaki = array(); $plecaki[0] = new Plecak($pojemnoscPlecaka); //wlasciwy algorytm //sortowanie paczek po wadze function sortuj(Paczka $a, Paczka $b) { if ($a->zwrocWage() == $b->zwrocWage()) return 0; else return ($a->zwrocWage() > $b->zwrocWage()) ? -1 : +1; } usort($paczki, 'sortuj'); //wkladanie paczek do plecaka $nr_plecak = 0; $plecak = $plecaki[$nr_plecak]; while($paczka = array_shift($paczki)) { if(($plecak->pozostalo >= $paczka->zwrocWage()) == false) { $plecaki[++$nr_plecak] = new Plecak($pojemnoscPlecaka); $plecak = $plecaki[$nr_plecak]; } $plecak->dodajPaczke($paczka); } foreach($plecaki as $p) { $p->zobaczPaczki(); } ?>
Problem plecakowy rozwiązany w ten sposób nie znajduje zawsze optymalnego rozwiązania, jednakże w bardzo wielu próbach rozwiązanie sugerowane przez algorytm jest poprawne.
Zostaw komentarz