### Knapsack Problem

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

**Solution:**

Max between taking an item or excluding an item

##### Recursive Formula:

Max {`value[index] + solveRecursiveHelper(weight, value, capacity - weight[index], index - 1) ,`

`solveRecursiveHelper(weight, value, capacity, index - 1`

}

##### DP Formula:

If`weight < weights[i - 1]`

then`table[i][weight] = table[i - 1][weight]`

Else`table[i][weight] = Math.max( values[i - 1] + table[i - 1][weight - weights[i - 1]], table[i - 1][weight])`

##### Recursive Algorithm:

- If index or capacity is zero then
- return 0

- If weights[index] > capacity then
- return 0

- Return Max { values[index] + recursive call with capacity – weights[index] or recursive call without current item) }

##### Dynamic Programming Algorithm:

- Create DP table of size (weights.length + 1) X (capacity + 1)
- Iterate index i 0 to weights.length + 1
`Iterate index j 0 to capacity + 1`

- If
`i or j equal to zero`

then- Set
`table[i][weight] = 0`

- Set
- Else If
`weight < weights[i - 1]`

then- Set
`table[i][weight] = table[i - 1][weight]`

- Set
- Else
- Set
`table[i][weight] = Math.max( values[i - 1] + table[i - 1][weight - weights[i - 1]], table[i - 1][weight]`

- Set

Latest Source Code:

Github: KnapsackProblem.java

**Output:**

Weights: [5, 4, 6, 3] Values: [10, 40, 30, 50] Capacity: 10 Max Value (By Recursion): 90 Max Value (By DP): 90