Question 5 When using Backtracking to solve the 0/1 Knapsack problem, each node of the state space solution tree contains 3 numbers: i) the profit accumulated, ii) the weight accumulated, and iii) the upper bound for this node (calculated by solving the problem, from this node on, as if it was a fractional knapsack one). Given the same 0/1 Knapsack instance as in question 3 above, solve it using the Backtracking technique by drawing the pruned state space tree solution and giving the maximum profit, and which objects will be chosen. Do not forget to sort first if you need to! P a b 60 16 24 с Capacity = 5 Tree W P/w 3 1 4 Max Profit = Objects chosen :

Question 5 When using Backtracking to solve the 0/1 Knapsack problem, each node of the state space solution tree contains 3 numbers: i) the profit accumulated, ii) the weight accumulated, and iii) the upper bound for this node (calculated by solving the problem, from this node on, as if it was a fractional knapsack one). Given the same 0/1 Knapsack instance as in question 3 above, solve it using the Backtracking technique by drawing the pruned state space tree solution and giving the maximum profit, and which objects will be chosen. Do not forget to sort first if you need to! P a b 60 16 24 с Capacity = 5 Tree W P/w 3 1 4 Max Profit = Objects chosen :