Question

[Recursive Cost] [ALGORITHM] Improving Efficiency

PLEASE explain in DETAIL the following question in detail. The algorithm is also given below. Thank You!

1.a) Define recursively the worst case cost Kn of the Knapsack function for n items. Remember that you need to provide both the base case and the recurrence relation. Also do not forget to include the cost of the function Worth in your cost. Justify your answer (i.e. explain what each component of the formula represents). [5points]

1.b)  Use iteration to find a formula for Kn which involves a sum (summation sign) [4points]

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

Answer 1

a) Knapsack vecurience then in YU (D iterative