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