Answer to Question #329708 in Algorithms for sandeep Lhs

Question

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

Profit 3 0 9 4

Weight 1 10 5 0

Answer 1

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