The 0/1 Knapsack Problem - Dynamic Programming

 References:
https://www.youtube.com/watch?v=EH6h7WA7sDw

 Class Item

class Item
{
 private $_weight;
 private $_value;
 
 public function __construct($value, $weight)
 {
  $this->_value = $value;
  $this->_weight = $weight;
 }
 
 public function getWeight()
 {
  return $this->_weight;
 }
 
 public function getValue()
 {
  return $this->_value;
 }
}

Fill v array and keep array

$capacity = 5;
$items = array();
$items[] = new Item(0, 0);
$items[] = new Item(5, 3);
$items[] = new Item(3, 2);
$items[] = new Item(4, 1);
//$items[] = new Item(6, 1);

$number_of_items = sizeof($items);
$keep = array();

for($w = 0; $w <= $capacity; $w++) 
{
 $v[0][$w] = 0;
 $keep[0][$w] = 0;
}

for($i = 1; $i < $number_of_items; $i++)
{
 for($w = 0; $w <= $capacity;$w++)
 {
  if($items[$i]->getWeight()<= $w)
  {
   if($v[$i-1][$w] > intval($items[$i]->getValue() + $v[$i-1][$w-$items[$i]->getWeight()]))
   {
    $v[$i][$w] = $v[$i-1][$w];
    $keep[$i][$w] = 0;
   }
   else
   {
    $v[$i][$w] = intval($items[$i]->getValue() + $v[$i-1][$w-$items[$i]->getWeight()]);
    $keep[$i][$w] = 1;
   }
  }
  else
  {
   $v[$i][$w] = $v[$i-1][$w];
   $keep[$i][$w] = 0;
  }
 }
}

Print out the max value of objects will fit in the knapsack

$maxValue = $v[$number_of_items-1][$capacity];
echo 'Max value '. $maxValue . "\n";
$value = 0;
$col = $capacity;
$line = $number_of_items-1;
$k = array();

while($maxValue > $value)
{
 if($keep[$line][$col]==1)
 {
  $value += $items[$line]->getValue();
  $k[] = $items[$line];
  $col = $col - $items[$line]->getWeight();
 }
  $line--;
}

Print out exactly which item:

foreach($k as $key => $value)
{
 echo "Item $key - Value:" . $value->getValue() . " Weight " . $value->getWeight() . "\n";
}