## 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.........

.