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();
}
?>

Działający przykład

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.