This problem is from SPOJ. Give it a try by following this link!
The simplified problem statement is as follows.
You need to collect some stamps from friends. Suppose you have n friends and each of them have some stamps with them {s1, s2, … sn}.
The problem is to find if we can collect the targeted number of stamps. If it is possible, we have to find the minimum number of friends to collect the stamps from.
For example. Let us assume we have a target of 100 stamps, and we have 5 friends with {27, 68, 39, 4, 51} stamps.
We just need to collect from 2 friends to achieve the target {68,51}.
The solution is simple.
- First check the sum of stamps from all the friends is sufficient to reach the target.
- If it is possible just sort the friends in descending order of the number of stamps they have.
- Keep collecting the stamps from them until have just enough stamps to reach the target.
Here is the C++ implementation of the above algorithm.