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. For this example, we do not need to introduce any types: all variables represent integer numbers, so we can rely on the built-in Int instead.

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	Int
TotalCoins	Int
OneCent	Int
TwoCent	Int
FiveCent	Int
TenCent	Int
TwentyCent	Int
FiftyCent	Int
OneEuro	Int
TwoEuro	Int

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

If we were to run the current implementation, we would encounter something very curious: the solver would be able to find a solution in which exactly one coin is used. Indeed, we have not yet specified that our number of coins must always be positive, so the solver can e.g. find solutions with -3 TwoCent coins. To overcome this, we add a constraint table as follows:

Coins
C+	TotalCoins	OneCent	TwoCent	FiveCent	TenCent	TwentyCent	FiftyCent	OneEuro	TwoEuro
1	≥ 0	≥ 0	≥ 0	≥ 0	≥ 0	≥ 0	≥ 0	≥ 0	≥ 0

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:

Model 1
==========
TotalMoney := 123.
TotalCoins := 4.
OneCent := 1.
TwoCent := 1.
FiveCent := 0.
TenCent := 0.
TwentyCent := 1.
FiftyCent := 0.
OneEuro := 1.
TwoEuro := 0.

Elapsed Time:
1.106

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

Model 1
==========
TotalMoney := 567.
TotalCoins := 7.
OneCent := 0.
TwoCent := 1.
FiveCent := 1.
TenCent := 1.
TwentyCent := 0.
FiftyCent := 1.
OneEuro := 1.
TwoEuro := 2.

Elapsed Time:
1.121