Over the past few months the Decision Management Community have created several challenges for users and vendors of Business Rules and Decision Management Systems to solve and submit.
For February-March the challenge is:
“How can a given amount of money be made with the least number of coins of given denominations?”
See the full description of the Feb-March Challenge
View all Previous Challenges
The PROIV Solution:
The PROIV solution has been created to avoid the issue caused by the ‘greedy algorithm’. This is the system by which the largest coin, which is not greater than the remaining value, is chosen until the goal amount is reached. This is not always the most efficient route if, for example, your coin denominations are 1, 3 and 4 and you want to make 6. The greedy algorithm would suggest 4+1+1 but the most efficient answer is 3+3
We have written a set of rules to analyse all possible coin combinations available to the sum, and then select the combination with the least components.
‘CalculatePermutations’ begins this process with the largest coins, then works down to explore for more efficient combinations. ‘FindMostEfficientCombinations’ uses a memory file to analyse the results and offers the first most efficient solution found. This avoids the Greedy Algorithm problem by still using the largest coins available.
For example, if the coin denominations are 1, 3 and 7 and you want to make 9, both 3+3+3 and 7+1+1 are correct answers. When answers like this compete, PROIV will suggest 7+1+1 because this is the first solution found.
This solution has been published as a REST Web Service, so the Coin Sorter can be accessed by other applications and devices.