[PSEUDOCODE] [ALGORITHM] Improving Efficiency

(7 marks) Make a few modifications to this algorithm to integrate the functionality of the Worth function directly into the recursion of Knapsack function in an efficient way that minimizes the number of references to the values array.

Use proper pseudocode. Also, just like in the original pseudocode provided, be sure to define all the variables and all the functions that you are using.

You will need to use Pairs in your pseudocode. A Pair is a data structures of the form p=(a,b). You would refer to the first element a as p[1] and the second element b as p[2] Attach your algorithm on a separate sheet.

Description of items is stored in arrays of n elements. Integer weightsIn] weights 3 weight of item i Integer values[n] values vaue of item i Set Knapsack anteger capacity, Integer n) capacity is the knapsack capacity n number of items to fit in the knapsack, n21 This function returns a set containing the most valuable combination of items which can fit in the knapsack Set Knapsack (nteger capacity, Integer n) If n-1 If weights[1] capacity return (1) Else return 0 lfitem n does not fit, leave it out Integer weightn weights[n If weig capacity return Knapsack (capacity, n-1) Best value when item n is included in knapsack Set included J (n) UKnapsack(capacity-weightn, n-1) Best value when item n is not included in knapsack Set excluded 3 Knapsack (capacity,n-1) If Worth excluded) Worth included) return excluded Else return included Integer Worth (Setofltems) Setofltems is a set of items This function returns the worth of a set of items Integer Worth (Setofltems) Integer result 0 For item in Setofltems do Result values item] Return result Additional Information: For the analysis that follows, you will be assuming that the basic operation is an array reference weights il or values i, i.e. you will be asked to count how many times an item is "touched". These references to the basic operation have been highlighted in the code. The size of this algorithm is n. Le. any description of the cost of this algorithm will be a function of n