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.
P02 is a set of N = 6 denominations (US coinage) with a target of 96.
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.
P04 is a set of N = 3 denominations with a target of 6. This is a simple example where the greedy algorithm fails.
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.
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.