(a) Give a dynamicprogramming solution to the 0-1 knapsack problem that runs in
ID: 3612282 • Letter: #
Question
(a) Give a dynamicprogramming solution to the 0-1 knapsack problem that runs in O(nW)time, where n is the number of items and W is the maximum weight ofitems that the thief can put in the knapsack.(b) Apply your algorithm to the problem when n = 4, W = 10, thevalue of items are v1 = 20, v2 = 60, v3 = 80, v4 = 100, and theweight items are w1 = 2, w2 = 4, w3 = 5, w4 = 7.
(a) Give a dynamicprogramming solution to the 0-1 knapsack problem that runs in O(nW)time, where n is the number of items and W is the maximum weight ofitems that the thief can put in the knapsack.
(b) Apply your algorithm to the problem when n = 4, W = 10, thevalue of items are v1 = 20, v2 = 60, v3 = 80, v4 = 100, and theweight items are w1 = 2, w2 = 4, w3 = 5, w4 = 7.
Explanation / Answer
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 weight of 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 could steal assumingthat he may selected only among the first I objects and that he hasa knapsack of size u. So we have to do thepseudocode for a dynamic programming algorithm to solve thisproblem. our algorithm need not determine the actual items tobe stolen, just the maximum value.
The dynamic programming solution to the 0/1 knapsack is similar innature to the Longest Common Subsequence problem, and others indynamic programming. A table is created, representing thechoice of items (in ascending order of weights w1wn), and agradually increasing size of knapsack, w. The first row isinitialized to 0, as the knapsack cannot hold any items. Thefirst column is initialized to 0, as there are no items 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, the value to the left is taken,represented by the  symbol. For the cellsin which wi  w areassigned the maximum of the item value 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 vi bytaking 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) = 220 ITS HELPFUL TO YOU.........
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.