There are a number of toys lying in from of him, tagged with their prices. Mark has an only a certain amount to spend, and he wants to maximize the number of toys he buys with his money. Given a list of toy prices and a amount to spend, determine the maximum number of gift he can buys. Each toy can only be purchased once.
Considerations
- There are a number of toys tagged with their prices. It means we have an slice
[1 4 7 3 4 9]. - Certain amount to spend,
7. It means we have a target. - Maximize the number of toys he can buy.
Combinatorial problems?
A combinatorial problem consists in, given a finite collection of objects and a set of constraints, finding an object of the collection that satisfies all constraints
Let rephrase the problem to something like this:
- Find all combinations in an slice that are equal or less than a target.
- Then, choice the largest one. And return their size
But do we care about the combinations? do we need to find them all?. The truth is that, it would be a waste of effort. Leading to an unnecessary increasing complexity and and extrange solutions.
A little more Thinking
What we really need is to find the largest combination and return their size. My original thinking was wrong I couldn’t build a solution that was easy to reason about and satisfy all the requirements.
Greedy algorithms
Greedy is an algorithm paradigm that build up a solution piece by piece, always choosing the next piece that offers the most obvios and immediate benefits. So the problems where choosing locally optimal also leads to global solution are the best fit for greedy.
Characteristics of Greedy algorithm
- There must be an ordered list of resources
- Maximum of all the resources are taken
It is called greedy because it tries to find the solution by making the best choice at each stage, without considering the future steps or the consequences of the current decision.