# Knapsack Problem

### 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:
1. If index or capacity is zero then
1. return 0
2. If weights[index] > capacity then
1. return 0
3. Return Max { values[index] + recursive call with capacity – weights[index] or recursive call without current item) }
##### Dynamic Programming Algorithm:
1. Create DP table of size (weights.length + 1) X (capacity + 1)
2. Iterate index i 0 to weights.length + 1
1. `Iterate index j 0 to capacity + 1`
2. If` i or j equal to zero` then
1. Set `table[i][weight] = 0`
3. Else If` weight < weights[i - 1]` then
1. Set `table[i][weight] = table[i - 1][weight]`
4. Else
1. Set `table[i][weight] = Math.max( values[i - 1] + table[i - 1][weight - weights[i - 1]], table[i - 1][weight]`

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
```
Author: