Knapsack Problem

The knapsack problem (a.k.a rucksack problem) is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

									function KnapSack($capacity, $weight, $value, $itemsCount)
{
	$K = array();

	for ($i = 0; $i <= $itemsCount; ++$i)
	{
		for ($w = 0; $w <= $capacity; ++$w)
		{
			if ($i == 0 || $w == 0)
				$K[$i][$w] = 0;
			else if ($weight[$i - 1] <= $w)
				$K[$i][$w] = max($value[$i - 1] + $K[$i - 1][$w - $weight[$i - 1]], $K[$i - 1][$w]);
			else
				$K[$i][$w] = $K[$i - 1][$w];
		}
	}

	return $K[$itemsCount][$capacity];
}

Example

									$value = array(60, 100, 120);
$weight = array(10, 20, 30);
$capacity = 50;
$itemsCount = 3;

$result = KnapSack($capacity, $weight, $value, $itemsCount);

Knapsack Problem

Example

Output