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[0]=B[1]=B[2]=...=B[15]=0k=1B[15]=max(B[15],B[151]+3)=3B[14]=max(B[14],B[141]+3)=3...B[1]=max(B[1],B[11]+3)=3k=2B[15]=max(B[15],B[1510]+0)=3B[14]=max(B[14],B[1410]+0)=3...B[11]=max(B[11],B[1110]+0)=3B[10]=max(B[10],B[1010]+0)=3k=3B[15]=max(B[15],B[155]+9)=12B[14]=max(B[14],B[145]+9)=12...B[6]=max(B[6],B[65]+9)=12B[5]=max(B[5],B[55]+9)=9k=4B[15]=max(B[15],B[150]+4)=16B[14]=max(B[14],B[140]+4)=16...B[1]=max(B[1],B[10]+4)=7B[0]=max(B[0],B[00]+4)=4Max  profit  is  16B\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