The capacity of a knapsack is 13. Solve the following 0-1 knapsack problem. Items (i, profit p_i, we ...

---

The capacity of a knapsack is 13. Solve the following 0-1 knapsack problem. Items (i, profit p_i, weight w_i, p_i/w_i): (1, $20, 2, $10), (2, $30, 5, $6), (3, $35, 7, $5), (4, $12, 3, $4), (5, $3, 1, $3). Use (a) the backtracking algorithm, (b) breadth-first search with branch and bound pruning, and (c) best-first search with branch and bound pruning. All algorithms use the optimal fractional knapsack algorithm to compute the upper bound of the profit. Show the actions step by step, including how the bound is calculated for each node.