Ways to exchange coins

Let's consider the implementation of an algorithm for calculating the number of ways to exchange a given amount using specified coin denominations.

Introduction

The algorithm for calculating the number of ways to exchange coins solves the problem of calculating the number of ways to represent a given amount of money using different coin denominations. This is a classic dynamic programming problem that is often used in combinatorics and economic models.

Function `changes`

Function changes calculates the number of ways to change a given amount (amount) using the available coin denominations (coins).

Parameters:

amount: integer — the amount to be exchanged
coins: array of integers — denominations of available coins

Returns:

A number of the type Int128 — the number of exchange methods

function changes(amount::Int, coins::Array{Int})::Int128
    # Creating an array to store the number of ways to change each amount from 0 to amount
    # Indexing starts at 1, so the size of the array is amount + 1
    ways = zeros(Int128, amount + 1)

    # For a sum of 0, there is one way — not to use any coins.
    ways[1] = 1

    # We go through each coin
    for coin in coins
        # For each amount from `coin` to `amount`
        for j in coin+1:amount+1
            # Updating the number of ways: adding ways to get the amount (j - coin)
            ways[j] += ways[j - coin]
        end
    end

    # Returning the number of ways to change the amount `amount`
    return ways[amount + 1]
end

changes (generic function with 1 method)

# Examples of using the function

@show changes(100, [1, 2, 5, 10]);       # Exchange of 100 rubles using 1, 2, 5, 10-ruble coins
@show changes(100_000, [1, 5, 10]);    # Exchange of 100,000 rubles

changes(100, [1, 2, 5, 10]) = 2156
changes(100000, [1, 5, 10]) = 100020001

The main part

What does the program do?

The program calculates **how many different ways ** a certain amount of money can be exchanged using a limited set of coins.

For example, how many combinations of coins in denominations of 1, 2, 5, and 10 are there to get any amount up to 100 rubles?

How does it work? Step-by-step explanation:

Step 1: Initialization

We are creating an array ways, where ways[i] it will contain the number of ways to make up the amount. (i - 1) (due to indexing from unity to Julia).

At the start, we assume that there is one way to get the amount. 0 (take 0 coins):

Step 2: Dynamically update the values

For each coin, we update the values sequentially. ways. If we have a coin with a face value of, for example, 5 rubles, then:

the amount of 5 can be exchanged as 0 + 5 → increase ways[6] on ways[1]
sum of 10 as 5 + 5 → increase ways[11] on ways[6], etc .

Step 3: Why is this cycle order important?

The cycle runs through coins, and within it through amounts. This order ensures that we don't count the same coin combination twice (for example, 5+10 and 10+5 count as the same ways).

The result of the program

The program outputs the results of function calls via a macro @show, which automatically prints the expression and its value.

Conclusion

We have reviewed the implementation of an algorithm for calculating ways to exchange money. This algorithm is widely used in problems of combinatorics, financial modeling and testing of payment systems.

The example was developed using materials from Rosetta Code