# 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 a `Goal`

table, we can tell the system to optimize the TotalCoins constant.

Goal |
---|

Minimize TotalCoins |

And that’s it! With just 2 glossary tables, 3 decision tables and a `Goal`

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
```