Understanding change-making algorithm

by

To get all possible sets that elements are equal to ‘a’ or ‘b’ or ‘c’ (our coins) that sum up to ‘X’ you can:

  • Take all such sets that sum up to X-a and add an extra ‘a’ to each one.
  • Take all such sets that sum up to X-b and add an extra ‘b’ to each one.
  • Take all such sets that sum up to X-c and add an extra ‘c’ to each one.

So number of ways you can get X is sum of numbers of ways you can get X-a and X-b and X-c.

ways[i]+=ways[i-coin]

Rest is simple recurrence.

Extra hint:
at the start you can get set with sum zero in exactly one way (empty set)

ways = [1]+[0]*target

More Related Contents:

  1. Find common substring between two strings
  2. Sliding window maximum in O(n) time
  3. Implement pow(x,n)%d with integers only. (without making use of library functions) [duplicate]
  4. Cost of len() function
  5. What’s a good rate limiting algorithm?
  6. Pick N distinct items at random from sequence of unknown length, in only one iteration
  7. Find all combinations of a list of numbers with a given sum
  8. Why is Bubble Sort implementation looping forever?
  9. Edit Distance in Python
  10. Longest increasing subsequence
  11. Speed of calculating powers (in python)
  12. heapq with custom compare predicate
  13. How to trace the path in a Breadth-First Search?
  14. Finding index of nearest point in numpy arrays of x and y coordinates
  15. Rotate image and crop out black borders
  16. General bars and stars
  17. Python Integer Partitioning with given k partitions
  18. How to invert a permutation array in numpy
  19. What is the complexity of the sorted() function?
  20. Non biased return a list of n random positive numbers (>=0) so that their sum == total_sum
  21. “For” loop first iteration
  22. How to hash a string into 8 digits?
  23. NumPy grouping using itertools.groupby performance
  24. A set union find algorithm
  25. Finding the most frequent character in a string
  26. Sieve of Eratosthenes – Primes between X and N
  27. How can I fit a Bézier curve to a set of data?
  28. Handling big numbers in code
  29. What is this odd sorting algorithm?
  30. counting combinations and permutations efficiently

Leave a Comment