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

Wiki