Data for the Change Making Problem

**CHANGE_MAKING**
is a dataset directory which
contains some examples of data for the change making problem.

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.

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

BIN_PACKING, a dataset directory which contains examples of the bin packing problem, in which a number of objects are to be packed in the minimum possible number of uniform bins;

CHANGE_MAKING, a MATLAB library which considers the change making problem, in which a given sum is to be formed using coins of various denominations.

GENERALIZED_ASSIGNMENT, a dataset directory which contains test data for the generalized assignment problem;

KNAPSACK, a FORTRAN77 library which solves a variety of knapsack problems.

KNAPSACK_01, a dataset directory which contains test data for the 0/1 knapsack problem;

KNAPSACK_MULTIPLE, a dataset directory which contains test data for the multiple knapsack problem;

PARTITION_PROBLEM, a dataset directory which contains examples of the partition problem, in which a set of numbers is given, and it is desired to break the set into two subsets with equal sum.

SUBSET_SUM, a dataset directory which contains examples of the subset sum problem, in which a set of numbers is given, and is desired to find at least one subset that sums to a given target value.

**P01** is a set of N = 5 denominations, with a target of 29.

- p01_c.txt, the target value.
- p01_w.txt, the denominations.
- p01_s.txt, the solution, given as a count for each denomination.

**P02** is a set of N = 6 denominations (US coinage) with a target of 96.

- p02_c.txt, the target value.
- p02_w.txt, the denominations.
- p02_s.txt, the solution, given as a count for each denomination.

**P03** is a set of N = 7 denominations (old British coinage) with a
target of 96. The greedy algorithm will not get the minimal solution.

- p03_c.txt, the target value.
- p03_w.txt, the denominations.
- p03_s.txt, the solution, given as a count for each denomination.

**P04** is a set of N = 3 denominations with a target of 6.
This is a simple example where the greedy algorithm fails.

- p04_c.txt, the target value.
- p04_w.txt, the denominations.
- p04_s.txt, the solution, given as a count for each denomination.

**P05** is a set of N = 6 denominations with a target of 100.
This is actually a version of a puzzle by Sam Loyd. In that puzzle,
an archery target has 6 rings, each with a numeric value, and
the archer wants to make a score of 100 exactly, firing as many
times as needed.

- p05_c.txt, the target value.
- p05_w.txt, the denominations.
- p05_s.txt, the solution, given as a count for each denomination.

**P06** is a set of N = 3 denominations with an (unattainable) target of 43.
This is actually a version of the "Chicken McNugget" problem.
At one time, McDonald's served Chicken McNuggets only in packages of
6, 9 and 20.

You can go up one level to the DATASETS directory.