0/1 Knapsack Problem
A knapsack has fixed capacity which needs to be filled with items in such a way that it will carry highest values (optimal load). This is a classical problem of DP (Dynamic Programming).
Embedded Files
Problem Defination:
Calculation:
m(1, 0)=0 ; //Base Case
m(1, 1) = 0 ; max[m(0,1)=0 , v1+m(0,0)=0+0 =0 ]
m(1, 2) =0 ; w1=5>j =2 ; ❎
m(1, 3) = 0 ; w1=5>j=3; ❎
m(1, 4) = 0 ; w1=5>j =4; ❎
m(1, 5) =21 ; w1=5=j =5; max[m(0,5)=0 , v1+m(0,0)=21+0 =21 ] ; ✅
m(1, 6) =21 ; w1=5<j =6; max[m(0,6)=0 , v1+m(0,0)=21+0 =21 ] ; ✅
m(2, 0)=0 ; //Base Case
m(2, 1) = 5 ; w2=1=j =1; max[m(1,1)=0 , v2+m(1,0)=5+0 =5 ] ✅
m(2, 2) =5 ; w2=1<j =2 ; max[m(1,2)=0 , v2+m(1,1)=5+0 =5 ]✅
m(2, 3) = 5 ; w2=1<j=3; max[m(1,3)=0 , v2+m(1,2)=5+0 =5 ] ✅
m(2, 4) = 5 ; w2=1<j =4; max[m(1,4)=0 , v2+m(1,3)=5+0 =5 ]✅
m(2, 5) =21 ; w2=1<j =5; max[m(1,5)=21 , v2+m(1,4)=5+0 =5 ]❎
m(2, 6) =26 ; w2=1<j =6; max[m(1,6)=21 , v2+m(1,5)=5+21 =26 ] ; ✅
m(3, 0)=0 ; //Base Case
m(3, 1) = 5 ; w3=3>j =1; m(2,1)=5; ❎
m(3, 2) =5 ; w3=3>j =2 ; m(2,2)=5; ❎
m(3, 3) = 13 ; w3=3=j=3; max[m(2,3)=5 , v3+m(2,0)=13+0 =13 ] ✅
m(3, 4) = 18 ; w3=3<j =4; max[m(2,4)=5, v3+m(2,1)=13+5 =18 ]✅
m(3, 5) =21 ; w3=3<j =5; max[m(2,5)=21 , v3+m(2,2)=13+5 =18 ]❎
m(3, 6) =26 ; w3=3<j =6; max[m(2,6)=26 , v3+m(2,3)=13+5 =18 ] ; ❎
m(4, 0)=0 ; //Base Case
m(4, 1) =5 ; w4=2>j =1; m(3,1)=5; ❎
m(4, 2) =9 ; w4=2=j =2 ; max[m(3,2)=5 , v4+m(3,0)=9+0 =9 ]; ✅
m(4, 3) = 14 ; w4=2<j=3; max[m(3,3)=13 , v4+m(3,1)=9+5 =14 ] ✅
m(4, 4) = 18 ; w4=2<j =4;max[m(3,4)=18, v4+m(3,2)=9+5 =14 ] ❎
m(4, 5) =22 ; w4=2<j =5; max[m(3,5)=21 , v4+m(3,3)=9+13 =22 ]✅
m(4, 6) = ; w4=2<j =6; max[m(3,6)=26 , v4+m(3,4)=9+18 =27 ] ; ✅
m(5, 0)=0 ; //Base Case
m(5, 1) = ; w5=4>j =1; m(4,1)=5; ❎
m(5, 2) = ; w5=4>j =2 ; m(4,2)=9 ; ❎
m(5, 3) = ; w5=4>j=3; m(4,3)=14 ❎
m(5, 4) = ; w5=4=j =4;max[m(4,4)=18, v4+m(4,0)=17+0 =18 ] ❎
m(5, 5) = ; w5=4<j =5; max[m(4,5)=22 , v4+m(4,1)=17+5 =22 ]✅
m(5, 6) = ; w5=4<j =6; max[m(4,6)=27 , v4+m(4,2)=17+9=27 ] ; ❎
Finding the Optimal Load:
m(i, j)={I4, I3, I2}
Page updated
Google Sites
Report abuse