Question

ALGORITHMS AND ANALYSIS

Show with a counterexample that the greedy approach does not always yield an optimal solution for the Change problem when the coins are U.S. coins and we do not have at least one of each type of coin.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

A set which forms a 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.

Kindly revert for any queries

Thanks.