Answers
A)0-1 Knapsack Problem (Dynamic-programmingsolution)
Given
A dynamic programming solution to the 0-1 knapsackproblem that runs in O(nW) time, where n is a number of items and Wis the maximum weightof items that the thief can put in hisknapsack. Hint: for i in [0..n] and u in [0..W], letV[i,u] be the maximum value that the thief couldsteal assumingthat he may selected only among the first I objects and that he hasa knapsack of size u.So we have to dothepseudocodefor a dynamic programming algorithm to solve thisproblem. our algorithm need not determine the actual items tobe stolen, just the maximumvalue.
The dynamic programming solution to the 0/1 knapsack is similar innature to the Longest Common Subsequence problem, and others indynamicprogramming. A table is created, representing thechoice of items (in ascending order of weights w1εwn), and agradually increasing size ofknapsack, w. The first row isinitialized to 0, as the knapsack cannot hold any items.
Thefirst column is initialized to 0, as there are noitems to put inthe knapsack. The cells are calculated using thefollowing formul
Algorithm Dynamic 1/0 Knapsack
Input: Two sequences of v = <v1,âεvn> and w= <w1âεwn>, n (number of items), W (maximumweight)
Output: the optimal value of the knapsack (not the actualitems)
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]
b)
The following example has the values and weights given below, witha knapsack capacity of 5. For those cells in whichwiÂ>Âw, thevalue to the left is taken,represented by the  symbol. For the cellsin which wiÂï‚£Âw areassigned the maximum of the itemvalue vi (taking the item)plus the V table one column to the left and ui rows up (thecalculated value of the items in a knapsack made smaller by vibytaking the item), and the value to the left (not taking theitem).
i
Value (vi)
Weight (wi)
1
60
1
2
100
2
3
120
3
Knapsack capacity (w)
Item 1
(v1 = 20, w1 = 2)
Item 2
(v2 = 60, w2 = 4)
Item 3
(v3 = 80, w3 = 5)
Item 4(v4=100,w4=7)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) = 220ITS HELPFUL TO YOU.........
.