Dear,
for i in [0..n] and u in [0..W],
let V[i,u] be the maximum value that the thief could steal assuming that he may selected only among the first i objects and that he has a knapsack of size u.
Give the pseudocode for a dynamic programming algorithm to solve this problem. Your algorithm need not determine the actual items to be stolen, just the maximum value.
The dynamic programming solution to the 0/1 knapsack is similar in nature to the Longest Common Subsequence problem, and others in dynamic programming.
A table is created, representing the choice of items (in ascending order of weights w1…wn), and a gradually increasing size of knapsack, w.
The first row is initialized to 0, as the knapsack cannot hold any items.
The first column is initialized to 0, as there are no items to put in the knapsack.
The cells are calculated using the following formula:
Algorithm Dynamic 1/0 Knapsack
Input: Two sequences of v = <v1,…vn> and w = <w1…wn>, n (number of items), W (maximum weight)
Output: the optimal value of the knapsack (not the actual items)
for w = 0 to W do
V[0,w] = 0
end-for
for i = 1 to n do
V[i,0] = 0
for w = 1 to W do
if wi ≤ w then
if vi + V[i-1,w-wi] > V[i-1,w] then
V[i,w] = vi + V[i-1,w-wi]
else
V[i,w] = V[i-1,w]
end-if
else
V[i,w] = V[i-1,w]
end-if
end-for
end-for
return V[n,W]
The following example has the values and weights given below, with a knapsack capacity of 5.
For those cells in which wi > w, the value to the left is taken, represented by the ← symbol.
For the cells in which wi ≤ w are assigned the maximum of the item value vi (taking the item) plus the V table one column to the left and ui rows up (the calculated value of the items in a knapsack made smaller by vi by taking the item), and the value to the left (not taking the item).
|
i
|
Value (vi)
|
Weight (wi)
|
|
1
|
60
|
1
|
|
2
|
100
|
2
|
|
3
|
120
|
3
|
|
Knapsack capacity (w)
|
|
Item 1
(v1 = 60, w1 = 1)
|
Item 2
(v2 = 100, w2 = 2)
|
Item 3
(v3 = 120, w3 = 3)
|
|
0
|
0
|
0
|
0
|
0
|
|
1
|
0
|
max(60+0,0) = 60
|
← 60
|
← 60
|
|
2
|
0
|
max(60+0,0) = 60
|
max(100+0,60) = 100
|
← 100
|
|
3
|
0
|
max(60+0,0) = 60
|
max(100+60,60) = 160
|
max(120+0,160) = 160
|
|
4
|
0
|
max(60+0,0) = 60
|
max(100+60,60) = 160
|
max(120+60,160) = 180
|
|
5
|
0
|
max(60+0,0) = 60
|
max(100+60,60) = 160
|
max(120+100,160) = 220
|