Why does the greedy coin change algorithm not work for some coin sets?

by

A set which forms a matroid (https://en.wikipedia.org/wiki/Matroid) can be used to solve the coin changing problem by using greedy approach. In brief, a matroid is an ordered pair
M = (S,l) satisfying the following conditions:

  1. S is a finite nonempty set
  2. l is a nonempty family of subsets of S, called the independent subsets,such that if B->l
    and A is a subset of B, then A -> l
  3. If A-> l, B-> l and |A| < |B|, then there is some element x-> B-A such that A U {x} ->l

In our question of coin changing, S is a set of all the coins in decreasing order value
We need to achieve a value of V by minimum number of coins in S

In our case, l is an independent set containing all the subsets such that the following holds for each subset: the summation of the values in them is <=V

If our set is a matroid, then our answer is the maximal set A in l, in which no x can be further added

To check, we see if the properties of matroid hold in the set S = {25,15,1} where V = 30
Now, there are two subsets in l:
A = {25} and B= {15,15}
Since |A| < |B|, then there is some element x-> B-A such that A U {x} ->l (According 3)
So, {25,15} should belong to l, but its a contradiction since 25+15>30

So, S is not a matroid and hence greedy approach won’t work on it.

More Related Contents:

  1. How to find all combinations of coins when given some dollar value [closed]
  2. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  3. SICP example: Counting change, cannot understand
  4. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  5. How to determine if a point is in a 2D triangle? [closed]
  6. Data structures for loaded dice?
  7. Writing your own square root function
  8. How to determine if a linked list has a cycle using only two memory locations
  9. Computing set intersection in linear time?
  10. Best word wrap algorithm? [closed]
  11. Finding closest neighbour using optimized Levenshtein Algorithm
  12. Selection algorithms on sorted matrix
  13. Euler project #18 approach
  14. How to calculate the index (lexicographical order) when the combination is given
  15. What algorithm for a tic-tac-toe game can I use to determine the “best move” for the AI?
  16. K-means algorithm variation with equal cluster size
  17. Hashing a Tree Structure
  18. Quicksort superiority over Heap Sort
  19. Best way of calculating n choose k?
  20. Why DFS and not BFS for finding cycle in graphs
  21. Finding multiple entries with binary search
  22. Painter puzzle – algorithmic estimation from first principles
  23. Polynomial time and exponential time
  24. Given a number, find the next higher number which has the exact same set of digits as the original number
  25. The best shortest path algorithm
  26. Algorithm for permutations of operators and operands
  27. Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location
  28. Compute the area of intersection between a circle and a triangle?
  29. Quadratic algorithm for 4-SUM
  30. CUDA stream compaction algorithm

Leave a Comment