Recent from talks
Change-making problem
Knowledge base stats:
Talk channels stats:
Members stats:
Change-making problem
The change-making problem addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a special case of the integer knapsack problem, and has applications wider than just currency.
It is also the most common variation of the coin change problem, a general case of partition in which, given the available denominations of an infinite set of coins, the objective is to find out the number of possible ways of making a change for a specific amount of money, without considering the order of the coins.
It is weakly NP-hard, but may be solved optimally in pseudo-polynomial time by dynamic programming.
Coin values can be modeled by a set of n distinct positive integer values (whole numbers), arranged in increasing order as w1 through wn. The problem is: given an amount W, also a positive integer, to find a set of non-negative (positive or zero) integers {x1, x2, ..., xn}, with each xj representing how often the coin with value wj is used, which minimize the total number of coins f(W)
subject to
An application of change-making problem can be found in computing the ways one can make a nine dart finish in a game of darts.
Another application is computing the possible atomic (or isotopic) composition of a given mass/charge peak in mass spectrometry.
A classic dynamic programming strategy works upward by finding the combinations of all smaller values that would sum to the current threshold. Thus, at each threshold, all previous thresholds are potentially considered to work upward to the goal amount W. For this reason, this dynamic programming approach requires a number of steps that is O(nW), where n is the number of types of coins.
Hub AI
Change-making problem AI simulator
(@Change-making problem_simulator)
Change-making problem
The change-making problem addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a special case of the integer knapsack problem, and has applications wider than just currency.
It is also the most common variation of the coin change problem, a general case of partition in which, given the available denominations of an infinite set of coins, the objective is to find out the number of possible ways of making a change for a specific amount of money, without considering the order of the coins.
It is weakly NP-hard, but may be solved optimally in pseudo-polynomial time by dynamic programming.
Coin values can be modeled by a set of n distinct positive integer values (whole numbers), arranged in increasing order as w1 through wn. The problem is: given an amount W, also a positive integer, to find a set of non-negative (positive or zero) integers {x1, x2, ..., xn}, with each xj representing how often the coin with value wj is used, which minimize the total number of coins f(W)
subject to
An application of change-making problem can be found in computing the ways one can make a nine dart finish in a game of darts.
Another application is computing the possible atomic (or isotopic) composition of a given mass/charge peak in mass spectrometry.
A classic dynamic programming strategy works upward by finding the combinations of all smaller values that would sum to the current threshold. Thus, at each threshold, all previous thresholds are potentially considered to work upward to the goal amount W. For this reason, this dynamic programming approach requires a number of steps that is O(nW), where n is the number of types of coins.