Compute 0/1 Knapsack problem for Total weight= 15 using dynamic programming.
Profit 3 0 9 4
Weight 1 10 5 0
"B\\left[ 0 \\right] =B\\left[ 1 \\right] =B\\left[ 2 \\right] =...=B\\left[ 15 \\right] =0\\\\k=1\\\\B\\left[ 15 \\right] =\\max \\left( B\\left[ 15 \\right] ,B\\left[ 15-1 \\right] +3 \\right) =3\\\\B\\left[ 14 \\right] =\\max \\left( B\\left[ 14 \\right] ,B\\left[ 14-1 \\right] +3 \\right) =3\\\\...\\\\B\\left[ 1 \\right] =\\max \\left( B\\left[ 1 \\right] ,B\\left[ 1-1 \\right] +3 \\right) =3\\\\k=2\\\\B\\left[ 15 \\right] =\\max \\left( B\\left[ 15 \\right] ,B\\left[ 15-10 \\right] +0 \\right) =3\\\\B\\left[ 14 \\right] =\\max \\left( B\\left[ 14 \\right] ,B\\left[ 14-10 \\right] +0 \\right) =3\\\\...\\\\B\\left[ 11 \\right] =\\max \\left( B\\left[ 11 \\right] ,B\\left[ 11-10 \\right] +0 \\right) =3\\\\B\\left[ 10 \\right] =\\max \\left( B\\left[ 10 \\right] ,B\\left[ 10-10 \\right] +0 \\right) =3\\\\k=3\\\\B\\left[ 15 \\right] =\\max \\left( B\\left[ 15 \\right] ,B\\left[ 15-5 \\right] +9 \\right) =12\\\\B\\left[ 14 \\right] =\\max \\left( B\\left[ 14 \\right] ,B\\left[ 14-5 \\right] +9 \\right) =12\\\\...\\\\B\\left[ 6 \\right] =\\max \\left( B\\left[ 6 \\right] ,B\\left[ 6-5 \\right] +9 \\right) =12\\\\B\\left[ 5 \\right] =\\max \\left( B\\left[ 5 \\right] ,B\\left[ 5-5 \\right] +9 \\right) =9\\\\k=4\\\\B\\left[ 15 \\right] =\\max \\left( B\\left[ 15 \\right] ,B\\left[ 15-0 \\right] +4 \\right) =16\\\\B\\left[ 14 \\right] =\\max \\left( B\\left[ 14 \\right] ,B\\left[ 14-0 \\right] +4 \\right) =16\\\\...\\\\B\\left[ 1 \\right] =\\max \\left( B\\left[ 1 \\right] ,B\\left[ 1-0 \\right] +4 \\right) =7\\\\B\\left[ 0 \\right] =\\max \\left( B\\left[ 0 \\right] ,B\\left[ 0-0 \\right] +4 \\right) =4\\\\\\\\Max\\,\\,profit\\,\\,is\\,\\,16"
Comments
Leave a comment