$(10$ marks$)$ Use the Best$-$First Search with Branch$-$and$-$Bound Pruning algorithm for

the $0-1$ Knapsack problem to maximize the profit for the following problem instance.

Show the pruned state space tree produced by using the Branch$-$and$-$Bound Pruning

algorithm. Specify the $$profit$,$weight$$ and $$bound$$ from top to bottom at each node in

the pruned state space tree $(6$ marks$).$ Mark each nonpromising node with a cross $(2$

marks$).$ Mark the node$($s$)$ with optimal solution $(1$ mark$).$ Mention the value and

solution of the problem $(1$ mark$).$

i pi wi

$1$ $$606$

$2$ $$9015$

$3$ $$10521$ W $=39$

$4$ $$369$

$5$ $$93$