Change-making Problem

Making change problems are a variety of partition of an integer problems where the allowed partition sizes may be restricted, i. e., the denominations available and whether the full amount is an available partition size (you can just hand the amount back).

You have an unlimited supply of cents, 5-cent pieces, dimes (worth 10 cents) and quarter dollars (worth 25 cents).

This problem is kept quite small so that one can verify easily that the answer is correct.

How many combinations, i. e., the order of the coins are not significant, are available to return twenty-five cents?

This is the answer to the question:

\( \left\{\left( \begin{array}{cc} 1 & 25 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 20 \\ 5 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 15 \\ 5 & 2 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 15 \\ 10 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 10 \\ 5 & 3 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 10 \\ 5 & 1 \\ 10 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 5 \\ 5 & 4 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 5 \\ 5 & 2 \\ 10 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 5 \\ 10 & 2 \\ \end{array} \right),\left( \begin{array}{cc} 5 & 5 \\ \end{array} \right),\left( \begin{array}{cc} 5 & 3 \\ 10 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 5 & 1 \\ 10 & 2 \\ \end{array} \right),\left( \begin{array}{cc} 25 & 1 \\ \end{array} \right)\right\} \)

And our final answer is 13. \( _\square \)

If the full range of permissible partitions is all positive integers less then or equal to amount to be returned, then, the total count would be the partition of an integer \(p(n)\).

Most change making problems encountered here can be done in the available coding environment herein.

For problems which are small enough to fit with the limits of arithmetic and allowed computation, a small recursive program can solve the problem.

In the Rust language:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

use std::collections::HashMap;

const SIZE: usize = 6;
// values must be positive and in descending order
static DENOMINATIONS: [i64; SIZE] = [100, 50, 25, 10, 5, 1];

fn coins(map: &mut HashMap<(i64,usize),i64>, amount:i64, index: usize)->i64 {
    if amount == 0 {
        return 1;
    }
    if amount < 0 {
        return 0;
    }
    // The amount has to be positive at this point.
    // the index being greater than size is an error
    if index > SIZE {
        return -1;
    }
    // the index being equal to SIZE means there is nothing left to be checked
    if index == SIZE {
        return 0;
    }
    if (*map).contains_key(&(amount,index)) {
        match map.get(&(amount,index)) {
            Some(&number) => return number,
            _             => return -1,
        }
    }
    let result1 = coins(map,amount-DENOMINATIONS[index],index);
    if result1 < 0 {
        return -1;
    }
    let result2 = coins(map,amount,index+1);
    if result2 < 0 {
        return -1;
    }
    let result = result1 + result2;
    if result < 0 {
        // the count overflowed!
        return -1;
    }
    (*map).insert((amount,index),result);
    return result;
}

fn main() {
    let mut map: HashMap<(i64,usize),i64> = HashMap::new();
    println!("coins returned {}",coins(&mut map,100,0));
}