CentralNotice Change-making problem From Wikipedia, the free encyclopedia Jump to: navigation , search The change-making problem addresses the following question: how can a given amount of money be made with the least number of coins of given denominations? It is a knapsack type problem , and has applications wider than just currency. 1 Mathematical definition 2 Non currency examples 3 Methods of solving 3.1 Simple dynamic programming 3.2 Dynamic programming with the probabilistic convolution tree 3.3 Linear programming 3.4 Greedy method 4 Related problems 5 See also 6 References Mathematical definition [ edit ] Coin values can be modeled by a set of n distinct positive integer values (whole numbers), arranged in increasing order as w 1 = 1 through w n . The problem is: given an amount W , also a positive integer, to find a set of non-negative (posi...