Please do all three questions and provide detailed explaination. Thanks!

$[0/1$ Knapsack$]$ Consider the knapsack problem discussed in class. We now add the

requirement that $x_i=1$ or $x_i=0,$AAi. That is$,$ an object is either completely included or not

included into the knapsack. We call this new version of knapsack problem as $0/1$ Knapsack

problem, and we still want to maximize the profit subject to the total weight $M.$

$($a$)$ One greedy strategy is: consider the objects in order of nonincreasing profit $p_i$; add the

object into the knapsack if it fits. Show that this strategy doesn't necessarily yield optimal

solutions.

$($b$)$ One greedy strategy is: consider the objects in order of nondecreasing weight $w_i$; add the

object into the knapsack if it fits. Show that this strategy doesn't necessarily yield optimal

solutions.

$($c$)$ One greedy strategy is: consider the objects in order of nonincreasing density $\frac{p_i}{w_i}$; add

the object into the knapsack if it fits. Show that this strategy doesn't necessarily yield optimal

solutions.