Myntproblem

Myntproblem, literally the coin problem in Swedish, refers to mathematical and computational problems that revolve around coin denominations and the amounts that can be formed with them. In its broad sense it includes questions such as finding the minimum number of coins needed to make a given value, counting how many distinct ways a value can be formed, and assessing whether a certain amount is attainable with a given set of denominations.

The most studied variant is the change-making problem: given coin denominations and a target value, minimize the number of coins used. Other variants include the coin system design problem, which asks how to choose denominations to achieve desirable properties, and the counting problem, which asks for the number of distinct representations of a value.

Theoretical results depend on the structure of the denominations. For some systems (canonical coin systems, such as typical currency where greedy choices are optimal) a simple greedy algorithm yields an optimal solution. For general denominations, dynamic programming yields a polynomial-time algorithm in the target value for a fixed set of denominations, while allowing the number of denominations to scale makes the problem NP-hard. The Frobenius coin problem, a classic related topic, seeks the largest value that cannot be formed when the gcd of denominations is one, and has explicit solutions only for specific cases (two coins, some three-coin families).

Applications of myntproblem include cash register optimization, resource allocation, and teaching algorithm design. It is a common topic in mathematics education, algorithm competitions, and operations research.