Change Making Decision Solutions
This month we have a simple challenge problem: 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.
Of course, you easily can solve this example without any tool (your children or grandchildren can do it too). We would like to see how your favorite Decision Management tool may help you to solve the problem in its generic formulation.
You may find a formal problem definition and different solving techniques at http://en.wikipedia.org/wiki/Change-making_problem. If your tool has difficulties to find an optimal solution, try to find at least one or several feasible solutions.
Send your solutions to DecisionManagementCommunity@gmail.com before March 1, 2015.
Solutions:
- JSR331 – submitted by Jacob Feldman, www.jsr331.org, Specification Lead
- Corticon – submitted by Michael Parish from Progress Corticon
- PROIV – submitted by Sadie Geen from www.proiv.com
- cDMN – submitted by Simon Vandevelde
- …
Note. In the US (and most other) coin systems, a greedy algorithm of picking the largest denomination of coin which is not greater than the remaining amount to be made will always produce the optimal result. This is not automatically the case, though: if the coin denominations were 1, 3 and 4, then to make 6, the greedy algorithm would choose three coins (4,1,1) whereas the optimal solution is two coins (3,3).
dmcommunity.org 