Reference no: EM133423601

Question: There are n libraries L₁, L₂, . . . , L_n. We want to store copies of a book in some of the libraries. Storing a copy at L_i incurs an integer purchase cost c_i > 0. A copy of the book is always stored at L_n. If a user requests the book from L_i and L_i does not have it, then L_i+1, L_i+2, . . . are searched sequentially until a copy of the book is found at L_j , for some j > i. This results in a user delay of j - i. (Note that, in this case, no library L_k with an index k smaller than i is searched; also, if the user finds the book at L_i , then the user delay is 0.) We define the total cost as the sum of all the purchase costs and all the user delays, assuming that there is one user in each of the n libraries. For example, if there are 4 libraries, and copies of the book are stored at L₁ and L₄, the total cost is c₁ + c₄ + 2 + 1. Give an efficient algorithm that returns (a) the minimum total cost; and (b) a set of libraries where copies of the books must be placed to achieve the minimum total cost.