Question

Solve the following instance of the 0/1 knapsack problem by using dynamic programming approach. Where W=5

item	weight	Value
1	3	SR 40
2	2	SR 6
3	1	SR 20
4	4	SR 12

Answer 1

Weight	3	2	1	4
Profit	40	6	20	12
item no	1	2	3	4
DP solu.	1	0	1	0

Note1: Comparing all leaf nodes possibility ,solution according to dynamic programming is (1,0,1,0)

(0,0) (12,4) (20,1) (32,5) (6,2) (18,6) (26,3) (38,7) (40,3) (52,7) (60,4) (72,8) (46,5) (58,9) (66,6) (78,10)

// Red mark are invalid bez w=5

(0,0) (12,4) (20,1) (32,5) (6,2) (26,3) (40,3) (60,4) (46,5)

// among this  (60,4) is giving solution according to dynamic programming.

Note2: we can solve this by table method also but in this way(tree) we can explore dynamic programming more efficiently.