change_making


change_making, a FORTRAN90 code which considers the change making problem, which counts the number of ways a given sum can be formed using coins of various denominations.

The change making problem is given a target value C and a set of N coin denominations with value W. The task is to determine the minimum number of coins needed to form the given value.

In the unbounded change making problem, there are a limitless supply of coins of each denomination. In the bounded change making problem, each denomination is available only up to some given limit.

For some sets of denominations, there will be target values that cannot be formed. (This relates to Frobenius's problem.)

A greedy algorithm for solving the change making problem repeatedly selects the largest coin denomination available that does not exceed the remainder. A greedy algorithm is simple, but it is not guaranteed to find a solution when one exists, and it is not guaranteed to find a minimal solution.

For certain sets of coin denominations, such as the US system of 1, 5, 10, 25, 50, 100, there is always a solution, and the greedy algorithm will always find the minimal solution.

For a set of coins such as the old British system, using 1, 2, 6, 12, 24, 48 and 60, there is always a solution, but the greedy algorithm will not always find the minimal solution.

For artificial systems such as 20, 25, 40, it is easy to see that there are many cases where there is no solution (you can't make ANY value that isn't a multiple of 5) but that the greedy will fail to find a solution for 50, even though that is easily formed as 25 + 25.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

change_making is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

change_making_test

change_making, a dataset directory which contains test data for the change making problem;

combination_lock, a FORTAN90 program which simulates the process of determining the secret combination of a lock.

combo, a FORTRAN90 code which includes many combinatorial routines.

football_scores, a Fortran90 code which counts the number of ways of achieving a given score in football.

KNAPSACK_01, a FORTRAN90 code which uses brute force to solve small versions of the 0/1 knapsack problem;

PARTITION_PROBLEM, a FORTRAN90 code which seeks solutions of the partition problem, splitting a set of integers into two subsets with equal sum.

SATISFY, a FORTRAN90 code which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem.

SUBSET, a FORTRAN90 code which enumerates, generates, ranks and unranks combinatorial objects including combinations, partitions, subsets, index sets, and trees.

SUBSET_SUM, a FORTRAN90 code which seeks solutions of the subset sum problem, in which it is desired to find a subset of a set of integers which has a given sum.

TSP_BRUTE, a FORTRAN90 code which reads a file of city-to-city distances and solves the traveling salesperson problem, using brute force.

Source Code:


Last revised on 07 June 2020.