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:
Ifweight < weights[i - 1]
thentable[i][weight] = table[i - 1][weight]
Elsetable[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