Question 1 [12 marks]: Consider the instance of discrete knapsack problem with the knapsack capacity 10 and the item information as follows: Item Weight Value 4 $1200 2 3 $6000 3 w $5100 $5400 Find the most valuable subset of the items that fits into the knapsack. Question 2 [12 marks]: A factory produces custom widgets according to customer requirements. It has several orders, each for a single widget. For each order, we know the following information: i) The profit that the factory will make from the order. ii) The deadline - the last day on which the customer will accept delivery. The factory can make exactly one widget per day. The following table shows all the orders for a 6-day period: Order No. 2 3 4 5 6 7 8 9 10 Profit 10 20 90 40 50 100 70 80 30 60 Deadline 6 6 3 4 2 3 4 Use Greedy Approach to determine the orders that the factory should accept and the schedule for producing the widgets of the accepted orders. Explain the result for each step in using the approach. Question 3 [12 marks]: Use divide-and-conquer strategy to design a recursive algorithm for finding the largest value (maximum) in a nonempty array of n numbers and specify it in recursive structure. Copyright SCIT, University of Wollongong, 2022 Page 2 of 4