How can a given amount of money be made with the least number of coins of given denominations?
Let S be a given sum that we want to achieve with a minimal amount of coins in denominations of x1, x2, …, xn. Here is a simple example: S is 123 cents, n is 4, x1 is 1 cent, x2 is 10 cents, x3 is 25 cents, and xn is 100 cents.
This seemingly simple problem turns out to be quite tricky in its most general form.
We’ll present two approaches to this.
The first makes a few reasonable assumptions about the data given that we are trying to make change for real people with real money – and this leads to quite a simple rule model that’s easy to understand.
The second shows a more generalized solution which requires more sophisticated rule modeling techniques and more computing resources.
This solution employs the “Greedy Algorithm”. I.e. successively subtracting the largest coin that does not exceed the amount remaining. http://en.wikipedia.org/wiki/Greedy_algorithm
This has the advantage that it’s very simple – just two rules - and it will find the optimal solution for normal currencies. However it is possible to choose coin values that will cause the greedy algorithm to fail. For example if the sum of lower value coins exceeds a higher value coin or if there is no 1 coin. This more complex case is discussed later.
This pair of rule sheets is executed repeatedly until no more rules can fire
The vocabulary is very simple. A single instance of Target to hold the amount and one or more instances of coin to hold the values to be used.
The .remove operator deletes the instance from memory.
The key to solving this challenge is the use of this expression
coin.value = coin.value->max
It does something very powerful.
The reference to coin means a specific instance of the collection of possible coins (as defined in the input data).
The second reference to coin means ALL the coins that are currently in memory. And the ->max operator finds the largest of them.
So the net result is that this statement identifies coin as the one with the largest value.
That particular coin is then used in the third condition to see if it’s less than or equal to the target amount. If it is then it value is subtracted from the amount remaining.
The rule flow diagram allows this process to repeat. It stops when no more rules fire.
Here is the test case referred to in the spec
NOTE: It is possible for there to be no solution when there is no 1 coin.
For example to make 123 from 10s, 25s and 100s (no 1’s) this is the best we can do:
But what about this test case:
There is a solution 100, 10, 9, 4 but the simple rules as specified do not find it.
Can you see a way to deal with this problem?
This problem can arise whenever the sum of two smaller values exceeds a larger value.
In this example 9+3 > 10 So we should consider using 9+3 before 10 (but only if 10 does not lead to a better solution)
In general we need to keep track of all possible combinations that could add up to the amount
In order to keep track of many possible combinations of coins we’ll employ a tree structure
The approach we’ll take in this rule model is to start with the target amount and then build a tree structure that represents all the possible ways that total amount can be constructed using the various coin values. You can see we have modeled a recursive structure in the vocabulary above to accommodate the possible coin values we could use at each step of the process.
Suppose the target is 6 and we have the following coins: 1, 3, 4. The Greedy Algorithm discussed earlier will find 4, 1, 1 as a solution, but that’s not the best. 3, 3 is the best.
Goal[1] is the starting point . Sub goals [2], [3] and [4] show the three possible choices of a first coin. Sub goal [3] (coin value =3) has a sub goal [5] (also coin value 3) which solves the problem. Once we have a solution we can stop creating sub goals. Only those sub goals that have an amount =0 are solutions.
Such a tree could get very large if you tried to use a lot of coins of value 1 to make up a large target value so we’ll add rules to discard poorer solutions as we go. It will record the best solution so far – any branch of the tree that is longer than that can safely be ignored. Basically, as soon as we find a solution we don’t need to keep expanding further sub goals.
The first rule sheet generates the next set of sub goals (one for each possible coin) for each current goal. It is repeated until it can reduce the target amount to zero (i.e. we have a goal amount of zero)
The second rule sheet simply finds the best result and displays it
Filter #1 prevents the rule sheet from executing once the problem is solved.
Filter #2 limits the coins considered to those whose values are less that the current goal amount.
Condition e checks if any goal exists with an amount of zero (which means we have a solution).
Condition f makes sure we don’t use the same coin more than once at each sub goal level. Though the same coin can be used at a different level.
Action B sets the isSolved attribute that stops the rule sheet from repeating forever
The result is displayed as a simple message:
Corticon will automatically use all the coin values in action B (you don’t have to write an explicit loop)
In this case with target amount of 20 and coins 1, 3, 4 a solution is found after 142 combinations.
Increasing the target amount by just one causes the search to consider 433 possibilities before finding a solution
As the gap between the target amount and the highest value coin increases, the number of combinations to be considered increases dramatically – eventually exceeding the memory capacity of the computer.
A more sophisticated (and probably more complex) algorithm is probably going to be required to solve the general case.
Some other test runs:
This rule sheet only goes one level deep
Whereas enabling the first condition causes it to recursively create sub goals:
Not entirely clear why this behavior occurs (though it is rather cool)