### Problem

Given a set of items, each with a weight and a value. Determine the maximum value of items to include in a collection so that the total weight is less than or equal to a given limit

### Example

Given 3 items with weights = {10, 20 , 30} and values = {60, 100, 120} respectively, knapsack weight capacity is 50. The maximum value of items to include in the knapsack is 220

### Dynamic programming approach

Have 2 options at each collecting step

- Including the
`i`

item if not exceeding the weight limit - Excluding the
`i`

item if exceeding the weight limit

### Implementation

Fill up a cache matrix `int[][] cache = new int[N+1][W+1]`

with

- 0 to
`N`

items as columns - 0 to
`W`

weight-limit as rows - each matrix cell
`cache[i][w]`

is the maximum value can be attained with weight less than or equal to`w`

using`i`

items

```
```

`i`

is the current item`w`

is the current weight limit`weights[i-1]`

is weight of current item as`int[] weights`

is 0 based index`values[i-1]`

is value of current item as`int[] values`

is 0 based index`cache[i][w]`

is maximum value of current item as`int[][] cache`

is 1 based index`weights[i-1] > w`

weight of the current item is more than the weight limit`cache[i][w] = cache[i-1][w]`

excludes the current item`cache[i-1][w-weights[i-1]] + values[i-1]`

includes the current item