# change_making

change_making, a C++ code which considers the change making problem, in which a given sum is to 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.

### 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, a dataset directory which contains test data for the change making problem;

COMBINATION_LOCK, a C++ code which simulates the process of determining the secret combination of a lock.

COMBO, a C++ code which includes many combinatorial routines.

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

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

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

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

SUBSET_SUM, a C++ 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 C++ code which reads a file of city-to-city distances and solves the traveling salesperson problem, using brute force.

### Source Code:

Last revised on 16 February 2020.