DMC Challenge

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.

p4-dmc-solution

‘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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s