On analysing the problem one finds that:

- There is no exact change for all odd values.
- The C value can be represented as sum of 1s.
- 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*|. - We define
*L*to be promising if it can be extended (by adding a list of coins) ...

Start Free Trial

No credit card required