2. (10 marks) Use the Breadth-First Search with Branch-and-Bound Pruning al. gorithm 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 (2 marks) Pi w 1 S60 6 2 S90 15 3 $105 21 4 S36 9 5 $93 W 39 3. (10 marks) Use the Best-First Search with Branch-and-Bound Pruning algo- rithm for the 0-1 Knapsack problem to maximize the profit for the problem instance of Question 2. Show the pruned state space tree produced by us- ing the Branch-and-Bound Pruning algorithm. Specify the 'profit', 'weight and 'bound' from top to bottom at each node in the pruned state s (6 marks). Mark each nonpromising node with a cross (2 marks). Mark the node(s) with optimal solution (2 marks) pace tree 2. (10 marks) Use the Breadth-First Search with Branch-and-Bound Pruning al. gorithm 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 (2 marks) Pi w 1 S60 6 2 S90 15 3 $105 21 4 S36 9 5 $93 W 39 3. (10 marks) Use the Best-First Search with Branch-and-Bound Pruning algo- rithm for the 0-1 Knapsack problem to maximize the profit for the problem instance of Question 2. Show the pruned state space tree produced by us- ing the Branch-and-Bound Pruning algorithm. Specify the 'profit', 'weight and 'bound' from top to bottom at each node in the pruned state s (6 marks). Mark each nonpromising node with a cross (2 marks). Mark the node(s) with optimal solution (2 marks) pace tree