Dynamic Programming-Knapsack Problem
Download as PPTX, PDF
3 likes842 views
The document discusses the 0/1 knapsack problem and dynamic programming algorithm to solve it. The 0/1 knapsack problem involves selecting a subset of items to pack in a knapsack that maximizes the total value without exceeding the knapsack's weight capacity. The dynamic programming algorithm solves this by building up a table where each entry represents the maximum value for a given weight. It iterates through items, checking if including each item increases the maximum value for that weight.
![Algorithm
Loop, for w0 to W(total capacity)
Set Kp[0,w] 0.
Loop, for i 1 to n(set of items)
Set Kp[i,0] 0.
Check whether K is a part of solution or not-
if (wi<=w)(can be part of the solution)
if (vi+kp[i-1,w-wi])>Kp(i-1,w)
Set kp[i,w] vi
+kp[i-1,w-wi]
Else
Set Kp[i,w] Kp[i-1,w]
Exit](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-4-320.jpg)
![i/w 0 1 2 3
0
1
2
3
for w 0 to W, for i1 to n
Set Kp[0,w] 0, Set Kp[i,0]0
i/w 0 1 2 3
0 0 0 0 0
1 0
2 0
3 0](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-6-320.jpg)
![i=1,vi=2,wi=1,w=1,w-wi=0
if (wi<=w), set kp[i,w] vi
+kp[i-1,w-wi]
Kp[1,1]2+Kp[0,0]=2
i/w 0 1 2 3
0 0 0 0 0
1 0
2 0
3 0
i/w 0 1 2 3
0 0 0 0 0
1 0 2
2 0
3 0](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-7-320.jpg)
![i=1,vi=2,wi=1,w=2,w-wi=1
if (wi<=w), set kp[i,w] vi
+kp[i-1,w-wi]
Kp[1,1]2+Kp[1,1]=2
i/w 0 1 2 3
0 0 0 0
0
1 0 2 2
2 0
3 0](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-8-320.jpg)
![i=1,vi=2,wi=1,w=3,w-wi=2
(wi<=w), Kp[1,3]2+Kp[0,2]=2
i=2,vi=3,wi=2,w=1,w-wi=-1
if (wi>w), Set Kp[i,w] Kp[i-1,w]
kp[2,1]Kp[1,1]=2
i/w 0 1 2 3
0 0 0 0 0
1 0 2 2 2
2 0 2
3 0](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-9-320.jpg)
![i=2,vi=3,wi=2,w=2,w-wi=0
(wi<=w), Kp[2,2]3+Kp[1,0]=3
i=2,vi=3,wi=2,w=3,w-wi=1
(wi<=w), Kp[2,3]3+Kp[1,1]=3+2=5
i/w 0 1 2 3
0 0 0 0 0
1 0 2 2 2
2 0 2 3 5
3 0](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-10-320.jpg)
![i=3,vi=4,wi=3,w=1,w-wi=-2
if (wi>w), Set Kp[i,w] Kp[i-1,w]=2
i=3,vi=4,wi=3,w=2,w-wi=-1
if (wi>w), Set Kp[i,w] Kp[i-1,w]=3
i/w 0 1 2 3
0 0 0 0 0
1 0 2 2 2
2 0 2 3 5
3 0 2 3](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-11-320.jpg)
![i=3,vi=4,wi=3,w=3,w-wi=0 (wi<=w),
if (vi+kp[i-1,w-wi])>Kp(i-1,w)=4<5
Kp[3,3]5
i/w 0 1 2 3
0 0 0 0 0
1 0 2 2 2
2 0 2 3 5
3 0 2 3 5](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-12-320.jpg)
![Now we have computed the maximum
possible values that can be taken in a
knapsack i.e Kp[n,W]
In order to select items that can take part
in making this maximum value let
i=n,k=W.](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-13-320.jpg)
![Algorithm
Set in
set kW
Loop to check K is a part of knapsack
while (i>0 and k>0)
if Kp[i,k]Kp[i-1,k] then
mark the ith item in knapsack
set i i-1
set k k-wi
Else
set i i-1
Exit](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-14-320.jpg)
![i=3,k=3,vi=4,wi=3,Kp[i,k]=5,Kp[i-1,k]=5
ii-1
i/w 0 1 2 3
0 0 0 0 0
1 0 2 2 2
2 0 2 3 5
3 0 2 3 5](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-15-320.jpg)
![i=2,k=3,vi=3,wi=2,Kp[i,k]=5,Kp[i-1,k]=2
Set kk-wi=1
Set ii-1
i/w 0 1 2 3
0 0 0 0 0
1 0 2 2 2
2 0 2 3 5
3 0 2 3 5](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-16-320.jpg)
![i=1,k=1,vi=2,wi=1,Kp[i,k]=2,Kp[i-1,k]=0
Set kk-wi=0
Set ii-1
i=0
K=0
i/w 0 1 2 3
0 0 0 0 0
1 0 2 2 2
2 0 2 3 5
3 0 2 3 5](https://image.slidesharecdn.com/dppresentation-151006163106-lva1-app6892/85/Dynamic-Programming-Knapsack-Problem-17-320.jpg)
Dynamic Programming-Knapsack Problem
- 2. Dynamic Programming It is a multistage optimizing decision making problem closely related to divide & conquer technique. It solves the sub-problem only once & stores the result in a table instead of solving it recursively.
- 3. 0/1 Knapsack Problem Given a set of n items and a knapsack having capacity w, each item has weight wi and value vi. The problem is to pack the knapsack in such a way so that maximum total value is achieved and the total weight should not be more than the fixed weight. The problem is called 0/1 knapsack because the items are either accepted or rejected.
- 4. Algorithm Loop, for w0 to W(total capacity) Set Kp[0,w] 0. Loop, for i 1 to n(set of items) Set Kp[i,0] 0. Check whether K is a part of solution or not- if (wi<=w)(can be part of the solution) if (vi+kp[i-1,w-wi])>Kp(i-1,w) Set kp[i,w] vi +kp[i-1,w-wi] Else Set Kp[i,w] Kp[i-1,w] Exit
- 5. Consider a knapsack with weight capacity W=3 and total items 3 such that S=3 wi={1,2,3} vi={2,3,4} On applying knapsack algorithm, Item wi vi 1 1 2 2 2 3 3 3 4
- 6. i/w 0 1 2 3 0 1 2 3 for w 0 to W, for i1 to n Set Kp[0,w] 0, Set Kp[i,0]0 i/w 0 1 2 3 0 0 0 0 0 1 0 2 0 3 0
- 7. i=1,vi=2,wi=1,w=1,w-wi=0 if (wi<=w), set kp[i,w] vi +kp[i-1,w-wi] Kp[1,1]2+Kp[0,0]=2 i/w 0 1 2 3 0 0 0 0 0 1 0 2 0 3 0 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 0 3 0
- 8. i=1,vi=2,wi=1,w=2,w-wi=1 if (wi<=w), set kp[i,w] vi +kp[i-1,w-wi] Kp[1,1]2+Kp[1,1]=2 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 2 0 3 0
- 9. i=1,vi=2,wi=1,w=3,w-wi=2 (wi<=w), Kp[1,3]2+Kp[0,2]=2 i=2,vi=3,wi=2,w=1,w-wi=-1 if (wi>w), Set Kp[i,w] Kp[i-1,w] kp[2,1]Kp[1,1]=2 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 2 2 0 2 3 0
- 10. i=2,vi=3,wi=2,w=2,w-wi=0 (wi<=w), Kp[2,2]3+Kp[1,0]=3 i=2,vi=3,wi=2,w=3,w-wi=1 (wi<=w), Kp[2,3]3+Kp[1,1]=3+2=5 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 2 2 0 2 3 5 3 0
- 11. i=3,vi=4,wi=3,w=1,w-wi=-2 if (wi>w), Set Kp[i,w] Kp[i-1,w]=2 i=3,vi=4,wi=3,w=2,w-wi=-1 if (wi>w), Set Kp[i,w] Kp[i-1,w]=3 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 2 2 0 2 3 5 3 0 2 3
- 12. i=3,vi=4,wi=3,w=3,w-wi=0 (wi<=w), if (vi+kp[i-1,w-wi])>Kp(i-1,w)=4<5 Kp[3,3]5 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 2 2 0 2 3 5 3 0 2 3 5
- 13. Now we have computed the maximum possible values that can be taken in a knapsack i.e Kp[n,W] In order to select items that can take part in making this maximum value let i=n,k=W.
- 14. Algorithm Set in set kW Loop to check K is a part of knapsack while (i>0 and k>0) if Kp[i,k]Kp[i-1,k] then mark the ith item in knapsack set i i-1 set k k-wi Else set i i-1 Exit
- 15. i=3,k=3,vi=4,wi=3,Kp[i,k]=5,Kp[i-1,k]=5 ii-1 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 2 2 0 2 3 5 3 0 2 3 5
- 16. i=2,k=3,vi=3,wi=2,Kp[i,k]=5,Kp[i-1,k]=2 Set kk-wi=1 Set ii-1 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 2 2 0 2 3 5 3 0 2 3 5
- 17. i=1,k=1,vi=2,wi=1,Kp[i,k]=2,Kp[i-1,k]=0 Set kk-wi=0 Set ii-1 i=0 K=0 i/w 0 1 2 3 0 0 0 0 0 1 0 2 2 2 2 0 2 3 5 3 0 2 3 5
- 18. The optimal knapsack contains S= {1,2} wi= {1,2}={3} <= W vi= {2,3}= {5}損 Optimum Value
- 19. THANKS!!!!