Q$2.(15$ points$)$ Use the Best$-$First Search with Branch$-$and$-$Bound

Pruning algorithm for the $0-1$ Knapsack problem to maximize the profit

for the following instance. Label the nodes according to the order in

which the nodes are created, expand all promising nodes

$,$ label the invalid nodes, and show all calculations and the final solution.

Item Pi Wi

$1$ $$606$

$2$ $$243$

$3$ $$213$

$4$ $$306$

$5$ $$205$ The maximum possible total weight $=14$