Christmas is approaching fast and Santa did not yet work on his gift distribution plan! For this, he seeks your help. Santa has one bag that can hold a maximum of Mkg in gifts’ weight. Each gift gi has a weight wi , and obviously Santa wants to take the maximum number of gifts he can hold. Given the weight and value of n gifts and the total weight, M, the bag can hold, Santa needs you to design an algorithm that tells him which gifts he should put in his bag such that the total number of gifts is maximized given that the total weight of the selected gifts should not exceed M. What is the worst-case running time of your algorithm? Justify.

Any idea how to solve this?