Mr. X wants to borrow some books from the library. He is carrying a bag with...

 

Transcribed Image Text:

Mr. X wants to borrow some books from the library. He is carrying a bag with capacity of W(kg). Each of the books in the library has a fixed weight. Multiple copies of the same books have the same weight. Like every other student in the world, Mr. X also does not like to read too many books. So, his target is to borrow as minimum number of books possible to fill-up his bag. The library allows to borrow books only if you fill up the bag to its full capacity. Given a list L, containing the weight of N different books, and the total capacity of the bag W, your goal is to find the minimum number of books Mr. X can borrow satisfying the condition explained above. You may assume there are infinite supply of each type of books. This problem can be solved using dynamic programming. Now answer the following questions: i. Define the set of subproblems and explain how they will contribute towards the complete solution. ii. iii. For a bottom-up approach find the initial values for the DP-table. (Students having Odd ID) OR For a top-down approach find the base cases for the recursive solution. (Students with even ID) Construct the DP-table for the input L (1,2,4) and W-5 Mr. X wants to borrow some books from the library. He is carrying a bag with capacity of W(kg). Each of the books in the library has a fixed weight. Multiple copies of the same books have the same weight. Like every other student in the world, Mr. X also does not like to read too many books. So, his target is to borrow as minimum number of books possible to fill-up his bag. The library allows to borrow books only if you fill up the bag to its full capacity. Given a list L, containing the weight of N different books, and the total capacity of the bag W, your goal is to find the minimum number of books Mr. X can borrow satisfying the condition explained above. You may assume there are infinite supply of each type of books. This problem can be solved using dynamic programming. Now answer the following questions: i. Define the set of subproblems and explain how they will contribute towards the complete solution. ii. iii. For a bottom-up approach find the initial values for the DP-table. (Students having Odd ID) OR For a top-down approach find the base cases for the recursive solution. (Students with even ID) Construct the DP-table for the input L (1,2,4) and W-5