Recall the that the knapsack problem is an optimization problem. The goal is to fill a knapsack with capacity W with the maximum value from a list of items each with weight and value. The discrete knapsack includes the restriction that items can not be spit, meaning the entire item or none of the item can be selected, the weights, values and capacity have integer values.
To design a dynamic programming algorithm we need to find a recursive relation from the smaller sub problems to larger problem.
Specify the weights and values in arrays w[1...n] and v[1...n]. This implies that we have listed the items in a sequence.
The sub problems i j is then be the knapsack problem for items 1, ... ,i with values v[1 ... i], weights w[1 ... i] and the capacity of the knapsack is j.
The value of the optimal solution is V[i, j]. The feasible solutions can be divided into two sets, those composed of only the i-1 proceeding items and those using the i-th item.
1. The optimal solution the for the sub problem that does not include the i-th item and capacity j is V[i-1, j].
2. The optimal solution for the sub set that include the i-th item can be written
V[i-1, j-w[i]] + v[i]
where j-w[i] should not be negative and assures that the sub-problem knapsack has remaining capacity to include the i-th item.
Then the recurrence relation is
V[i, j] = max{ V[i-1, j], V[i-1, j-w[i]] + v[i] } if j-w[i] ≥ 0
= V[i-1, j] if j-w[i] < 0
We need initial conditions (IC) and they are
V[0, j] = 0 for j ≥ 0 and V[i, 0] = 0 for i ≥ 0
which means that an empty knapsack has no value.
Then we can fill out V row wise
illustrate the algorithm
illustrate which previous cells are being used.
Cost is Θ(nW)
How would you construct the list of selected items?
Work backward and check the value above, meaning V[i-1, j].
If V[i-1, j] == V[i, j] then the i-th item was not chosen, so move on to V[i-1, j].
If V[i-1, j] ≠ V[i, j] then the i-th item was chosen, so move on to V[i-1, j-w[i]] + v[i].
Repeat the check.
What is the cost? Θ(n+W)
Dynamic programming solves problems that have a recurrence relation. Using the recurrences directly in a recursive algorithm is a top-down technique. It has the disadvantage that it solves common sub problem multiple times. This leads to poor efficiency, exponential. The dynamic programming technique is bottom-up, and solving all the sub-problems only once. This has the disadvantage that some of the sub-problems may not have been necessary to solve. Illustrate in the table. We would like to have the best of both worlds, i.e. all the necessary sub-problem solved only once. This is possible using memory functions.
The technique uses a top-down approach, recursive algorithm, with table of sub-problem solution. Before determining the solution recursively the algorithm checks if the sub problem has already been solved by checking the table. If the table has a valid value then the algorithm uses the table value else it proceeds with the recursive solution.
Memory function algorithm for the knapsack problem initializes V[i, j] to -1 except row 0 and column 0, which is initialize to 0.
Algorithm MFKnapsack(i, j) // i, j represent the sub problem
if V[i, j] < 0 // meaning not already calculated
if j < Weights[i] then
value ← MFKnapsack(i-1, j)
else
value ← max(MFKnapsack(i-1, j), Values[i] + MFKnapsack(i-1, j-Weights[i])
V[i, j] ← value // put valid value in the table for both cases
return V[i, j]
Illustrate in the table which values of the table are calculated
Note for figure 8.14 only 11 out of the 20 entries of V are necessary.