# 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);
```

### Output

` ``220`