Dynamic Programming: The Knapsack Problem!
The problem: Given a set of items with specific values and integer weights, and a knapsack of capacity C, find the maximum value of the set of items we can fit into the knapsack.
The approach: Let's call K(i, j) the max value of the subset of items from 1 through i that we can fit into a knapsack of capacity j. We can reduce this problem into a subproblem in several ways...
1) If i = 0, then we don't have any items, so the max value will be 0.
2) If j = 0, then we can't put any items into our knapsack because it has zero capacity. Then, the max value will be 0.
3) If the weight of the ith item is bigger than our capacity j, then we can just chuck our ith item since we can't put it into our knapsack at all. We can just work with the first i-1 items. Then K(i, j) is reduced to K(i-1, j).
4) If we can fit our ith item into our knapsack (in other words, if the weight of the ith item is smaller or equal to our capacity j), then we have two choices with the ith item: put it in our knapsack or chuck it. If we want to put it in our knapsack, then we are left with the subproblem K(i-1, j - weight of ith item). If we don't put it in, then we are left with the same subproblem from case 3, K(i-1, j). We should take the bigger of these values, so K(i, j) is reduced to the max of K(i-1, j - weight of ith item) and K(i-1, j).
That's it!
This approach is O(nC), where n is the number of items and C is the capacity of our knapsack. The code for the above solution is below (note the shifted indices):
static int[][] tab;
public static int knapsack(int[] values, int[] weights, int C) {
for(int i = 0; i < tab.length; i++) {
for(int j = 0; j < tab[0].length; j++) {
if(i == 0) tab[i][j] = 0;
else if(j == 0) tab[i][j] = 0;
else if(weights[i-1] > j) tab[i][j] = tab[i-1][j];
else tab[i][j] = Math.max(tab[i-1][j], values[i-1] + tab[i-1][j-weights[i-1]]);
}
}
return tab[values.length][C];
}
All code is on my Github - try running it yourself!
Source(s): Geeksforgeeks, OCW, Clemson
