Greediness: Sorting for Somewhat Success
While when first confronted with a problem, it may seem unqiue, and perhaps unsolvable, with time and research we can often find the moving parts behind a problem. These gears often grind similiarily to other problems we have solved. Approaches to algorithm design generally build on these abstract similiarities of solutions and problems so that a system of design, though diverse on a semantic or lexical level, share syntaxical structures and can help us make out the possible to solutions to new problems. The Eistelung effect is a phenomenon where such familiar strides may provide false comfort that lead away from appropriate decisions, clouding and closing minds with worn keys and disparate locks. Since this is meant to be helpful documentation, however, such troubles will (maybe) talk about another day.
Here's classic problem we can use to guide us through, given a set of denominations in some currency and an amount in said currency, what is the minimal collection of denominations we need to reach that amount?
This is also known as the money-change problem. An example: with coins worth 1, 5, and 10, what's the best way to change 28?
With 6 coins, 10, 10, 5, 1, 1, 1 we do it.
How can we write the code to solve this. One way to think about this problem, and the approach I'm expounding is this post is that when trying to make a greedy decision, i.e. a decision that leads us to an optimal solution, is to sort the different choices we can make any point in time according to some heuristic.
And like that, we can translate a problem solvable through greediness to the problem of determining what heuristic to sort our choices by. In this case, since we're trying to minimize the amount of currency used, descending by value since like the natural choice. With our denominations sorted, as we make change, all we have to do is choose the largest denomination that is equal to or less than the amount of change we have (left) to give.
Working out the above example verbally, at first we are given 28, our denominations (sorted) are 10, 5, 1.
With 20, we can use a 10, leaving 18.
With 18 we can use a 10, leaving 8.
Since 8 is less than 10, we can't use it, but we can use a 5, leaving 3.
Since 3 is less than 10 and 5, we can't use them, but we can use 1, until we've reached 28 in total change
I leave the code to the reader as an exercise.
Greediness as any moral compass might suggest, isn't always good, and in algoritm design the advice is no different. This happens when making a greedy choice changes things such that the next best choice can't be made. An example: In addition to the denominations 1, 5, and 10, if we have 9 aswell, a greedy solution will not be optimal for 28. The greedy solution would result in 6 coins, while another appoach would result in 4.
This other approach will be discussed in another post, soon.