Knapsack 0/1

knapsack01.php

<?php

echo "PHP Knapsack 1/0 problem \n";

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;
	}
}

function knapsack($items, $capacity){

	$n = sizeof($items);//number of items
	$keep = array();

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



	for($i = 1; $i < $n; $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;
			}
		}
	}

	$k = $capacity;

	for($i=1; $i<$n;$i++){
		if($keep[$i][$k]===1){
			echo sprintf("Item : %d - Value: %d - Weight: %d \n", $i, $items[$i]->getValue(),$items[$i]->getWeight());
			$k = $k - $items[$i]->getWeight();
		}
	}
	return $v[$n-1][$capacity];
}

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

echo knapsack($items, $capacity);