Design and analysis of Algorithms, 2nd Edition

D.2.5  Chapter 10: Greedy Algorithms

On analysing the problem one finds that:

1. There is no exact change for all odd values.
2. The C value can be represented as sum of 1s.
3. A possible algorithm is:

   Algorithm D.26 | Coinchange(N)

    

   1	[Makes change for N units using coins from A]
   2	const A ← the coinage set;
   3	L ← Ø;
   4	[L is the list holding the solution]
   5	s ← 0;
   6	[s is the sum of items in L]
   7	while s < N do
   8	x ← largest item in A such that s + x ≤ N;
   9	L ← L,x;
   10	s ← s + x;
   11	end
   12	return L;

   Let C = 30. Then the greedy solution is L = {25, 1, 1, 1, 1, 1}, while the optimal solution is: Opt = {10, 10, 10}, and |Opt| = 3 < 6 = |L|.

4. We define L to be promising if it can be extended (by adding a list of coins) ...