Coin changing algorithm

by

This is a classic dynamic programming problem (note first that the greedy algorithm does not always work here!).

Assume the coins are ordered so that a_1 > a_2 > ... > a_k = 1. We define a new problem. We say that the (i, j) problem is to find the minimum number of coins making change for j using coins a_i > a_(i + 1) > ... > a_k. The problem we wish to solve is (1, j) for any j with 1 <= j <= n. Say that C(i, j) is the answer to the (i, j) problem.

Now, consider an instance (i, j). We have to decide whether or not we are using one of the a_i coins. If we are not, we are just solving a (i + 1, j) problem and the answer is C(i + 1, j). If we are, we complete the solution by making change for j - a_i. To do this using as few coins as possible, we want to solve the (i, j - a_i) problem. We arrange things so that these two problems are already solved for us and then:

C(i, j) = C(i + 1, j)                         if a_i > j
        = min(C(i + 1, j), 1 + C(i, j - a_i)) if a_i <= j

Now figure out what the initial cases are and how to translate this to the language of your choice and you should be good to go.

If you want to try you hands at another interesting problem that requires dynamic programming, look at Project Euler Problem 67.

More Related Contents:

  1. Algorithm to find Largest prime factor of a number
  2. How to make rounded percentages add up to 100%
  3. Write a function that returns the longest palindrome in a given string
  4. How do I efficiently determine if a polygon is convex, non-convex or complex?
  5. Cycles in an Undirected Graph
  6. Efficiently find binary strings with low Hamming distance in large set
  7. Roulette wheel selection algorithm [duplicate]
  8. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  9. Calculating mid in binary search
  10. Geo Fencing – point inside/outside polygon
  11. Find the missing and duplicate elements in an array in linear time and constant space
  12. Best Compression algorithm for a sequence of integers
  13. Smoothing data from a sensor
  14. A simple explanation of Naive Bayes Classification [closed]
  15. Basic Recursion, Check Balanced Parenthesis
  16. Euler project #18 approach
  17. Fastest available algorithm for distance transform
  18. Generating integers in ascending order using a set of prime numbers
  19. Big O when adding together different routines
  20. Sign of a symbolic algebraic expression
  21. Shortest path to transform one word into another
  22. Algorithm to simplify a weighted directed graph of debts
  23. What is the best way to check the strength of a password?
  24. Algorithm for merging two max heaps?
  25. Why is vector array doubled?
  26. maximum subarray of an array with integers [duplicate]
  27. Can brute force algorithms scale?
  28. What is the algorithm that opencv uses for finding contours?
  29. Find XOR of all numbers in a given range
  30. Best algorithm for matching colours.

Leave a Comment