change_diophantine

change_diophantine, a MATLAB code which sets up a Diophantine equation to solve 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.)

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

change_diophantine is available in a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

change_diophantine_test

diophantine_nd, a MATLAB code which is given a Diophantine equation in N variables, and returns all strictly positive solutions, or all nonnegative solutions.

matlab_combinatorics, a MATLAB code which considers a variety of problems in combinatorics involving counting, combinations, permutations, and so on.

Source Code:

• diophantine_nd_check.m, checks that a given Diophantine problem is well posed.
• diophantine_nd_nonnegative.m, returns all nonnegative solutions of a Diophantine equation in N variables.
• diophantine_equation_print.m, prints the data associated with a Diophantine equation.
• diophantine_solution_print.m, prints the solutions associated with a Diophantine equation.