Change Making

This page details the cDMN implementation of the Change Making challenge, as listed on https://dmcommunity.org/challenge/challenge-feb-2015/. The challenge is as follows:

Change Making

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 is a pretty cool example, as it shows the mathematical power of the cDMN solver. It is also a great example to show how cDMN is able to optimize values.

We start by making the glossaries. Firstly, we’re going to need a type to represent a range of numbers. We need to do this, because the cDMN solver can’t reason with unbounded numbers.

Type
Name Type Values
Number int [0, 1000]

To represent the number of coins, we will use a constant for each denomination. We will also use a constant to keep track of the total amount of coins, and the total amount of money.

Constant
Name Type
TotalMoney Number
TotalCoins Number
OneCent Number
TwoCent Number
FiveCent Number
TenCent Number
TwentyCent Number
FiftyCent Number
OneEuro Number
TwoEuro Number

Now that our glossary is finished, we can move on to the decision tables. We will be creating three tables which consist exclusively of output columns.

The first one is the total amount of money which we want to find the optimal assignment for. This is easily represented as:

Total
U TotalMoney
1 123

Next up, we want a way to represent the following formula: TotalMoney = OneCent * 1 + TwoCent * 2 + .... Using a decision table with the C+ hit policy, we can model this as:

Change
C+ TotalMoney
1 OneCent * 1
2 TwoCent * 2
3 FiveCent * 5
4 TenCent * 10
5 TwentyCent * 20
6 FiftyCent * 50
7 OneEuro * 100
8 TwoEuro * 200

Similarly, to count the amount of total coins:

Coins
C+ TotalCoins
1 OneCent
2 TwoCent
3 FiveCent
4 TenCent
5 TwentyCent
6 FiftyCent
7 OneEuro
8 TwoEuro

Now all that is left to do, is specify what we want to do with this model. There are multiple solutions possible, but we want the solution with the optimal amount of coins By creating an Execute table, we can tell the system to optimize the TotalCoins constant.

Execute
Minimize TotalCoins

And that’s it! With just 2 glossary tables, 3 decision tables and an execute table, we were able to model an optimal change making algorithm. If we run this in the cDMN solver, we get the following output:

Number of models: 1
Model 1
=======
structure  : V {
  FiftyCent = 0
  FiveCent = 0
  OneCent = 1
  OneEuro = 1
  TenCent = 0
  TotalCoins = 4
  TotalMoney = 123
  TwentyCent = 1
  TwoCent = 1
  TwoEuro = 0
}

Elapsed Time:
0.122001

If we want to look for the optimal way to form 567 cents, the cDMN solver outputs the following:

Number of models: 1
Model 1
=======
structure  : V {
  FiftyCent = 1
  FiveCent = 1
  OneCent = 0
  OneEuro = 1
  TenCent = 1
  TotalCoins = 7
  TotalMoney = 567
  TwentyCent = 0
  TwoCent = 1
  TwoEuro = 2
}

Elapsed Time:
0.128642