Question 2 [10 marks]:

Consider the instance of discrete knapsack problem with the knapsack capacity 40 and the item information as follows:

Item Weight Value

A 30 $1800

B 20 $1160

C 20 $1160

D 8 $360

Find the most valuable subset of the items that fits into the knapsack using Greedy Approach. Is the resulting solution the optimal solution? Verify informally and give the reason to justify of your answer.

Find the most valuable subset of the items that fits into the knapsack using Greedy Approach. Is the resulting solution the optimal solution? Verify informally and give the reason to justify of your answer.