Question Three

a$.$ Distinguish between the Knapsack problem and the $0/1$ Knapsack problem.

b$.$ Consider the following instance of the Knapsack problem

$[3]$

$N=7,M=15,(p_1,p_2,p_3,p_4,p_5,p_6,p_7,)=(10,5,15,7,6,18,3)$

$(w_1,w_2,w_3,w_4,w_5,w_6,w_7)=(2,3,5,7,1,4,1).$ Find the optimal solution for,

i$.$ Maximum profit.

ii$.$ Minimum weight.

$[4]$

iii. Maximum profit per unit weight.

$[4]$

$[4]$