Answer to Question #329708 in Algorithms for sandeep Lhs

Question #329708

Compute 0/1 Knapsack problem for Total weight= 15 using dynamic programming.


Profit 3 0 9 4

Weight 1 10 5 0




1
Expert's answer
2022-04-18T15:20:04-0400

"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"


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS