Question $2[10$ Marks$]$

The Knapsack problem was introduced in Chapter $3($Brute Force$)$ as an

optimization problem, the problem can be solved by Dynamic Programming and

the recurrence relation for the problem can be used in the Dynamic Programming

as described in the Dynamic Programming Chapter $($See the Slides$).$

Your task is to demonstrate how this algorithm works. To do that, suppose you

are given the knapsack problem illustrated in the table below, apply the dynamic

programming technique to find the optimal solution. Give the details of the

optimal solution $($which items to be selected, their total value and total size$).$