Conference rusure::math

>Will this always create a minimal total number of coins for a requested amount?
>If it will, then how can I prove this?  If it will not, then for what values
>will this not work?

	I can't think of a counter-example for this particular table
	of coin values.  But there are tables for which this process
	is not minimal.  For example, with a[n] = {10,6,1} you will
	use three coins making change for 12 (i.e., 10, 1, and 1)
	instead of the minimal two coins (6 and 6).

	Can you prove anything in general if each coin has at least
	twice the value of the next coin?

	Dan

    Dan,
    
    Thanks for the specific instance of where the process fails.
    
<	Can you prove anything in general if each coin has at least
<	twice the value of the next coin?
    
    Supposedly, if this is the case, the number of coins generated will be
    the minimal amount.  How can it be proved?   
    
    I imagine the following might have something to do with it.  If 
    
      a[n] = {2^k-1, 2^k-2, 2^k-3...,2^1,2^0}
    
    Let c be the amount to represent using the coins in A[n].
    Then 0 <= c <= (2^k)-1 if each coin is used only once.  
    
    scott

RE: .2 (scot re: .1 Dan)

><	Can you prove anything in general if each coin has at least
><	twice the value of the next coin?
>    
>    Supposedly, if this is the case, the number of coins generated will be
>    the minimal amount.  How can it be proved?

    It cannot because it is not true.  Let the coins be {21, 10, 1}.  Each
    coin in the sequence is at least twice the next.  Given a request for
    30� the algorithm will produce:

		1*21� + 9*1� = 10 coins

    instead of:

		3*10� = 3 coins

    So what are the characteristics of a coin sequence which will make the
    algorithm optimal?

    A sufficient, but I suspect not necessary, condition is that each coin
    be evenly divisible by the next smaller coin.  The proof is straight-
    forward.

    By the way, algorithms of this form are known as "greedy algorithms".

						Topher

    
    What if a(n) is {k^n-1, k^n-2, k^n-3,...,k,k^0}?  Will the number of
    coins generated be the minimal number?
    
    scott

.4> What if a(n) is {k^n-1, k^n-2, k^n-3,...,k,k^0}?  Will the number of
.4> coins generated be the minimal number?

    For this one, yes.  For any amount of money, the min-change solution
    will contain fewer than k of any denomination (except perhaps the
    k^(n-1) denomination); if it contained k or more coins, k of them could
    be exchanged for the next higher denomination.  Given this constraint,
    the min-change solution is unique (think of it as a radix-k number).

    Now it's easy to see that the greedy algorithm yields the same solution,
    though the highest denomination must be handled with some care:
    The k^(n-2) thru k^0 denominations contribute at most k^(n-1)-1 to the
    sum, thus the min-change solution must use as many k^(n-1) coins as
    possible, which is just what the greedy algorithm does.

.3> A sufficient, but I suspect not necessary, condition is that each coin
.3> be evenly divisible by the next smaller coin.  The proof is straight-
.3> forward.

.0> Will this always create a minimal total number of coins for a requested amount?
.0> a[n] = {50,25,10,5,1};  a[i] table.

Yes, it will.  Suppose the amount is N.  The number of "1"s in the change
is N mod 5 -- if there were more than 5, replace 5 of them with a "5" coin.

As for the other coins, in a min-change solution, there may only be 0 or 1
"25"s, 0 to 2 "10"s, and 0 or 1 "5"s.

	25 10  5   Sum
	-- -- --   ---
	 0  0  0    0
	 0  0  5    5
	 0 10  0   10
	 0 10  5   15
	 0 20  0   20
	 0 20  5   25	("25" is better)
	25  0  0   25
	25  0  5   30
	25 10  0   35
	25 10  5   40
	25 20  0   45
	25 20  5   50

Thus, we see that it's never best to give fewer than the maximum number of
"50" coins -- the min-change solution couldn't possibly absorb them (only
one entry above is for 50� or more, and that one is clearly not part of a
min-change solution).

Now all the other choices for min-change are forced, except for the two
possibilities for 25�.  And for that, the greedy algorithm gives the
optimal change.

.3>  So what are the characteristics of a coin sequence which will make the
.3>  [greedy] algorithm optimal?

Consider the three coin sequence {c,b,1}, with c > b > 1.  The greedy
algorithm can fail iff the b and c satisfy:

	(c-1) div b + (c-1) mod b < (b-1)

This is a surprisingly pretty result!  ...which I discovered via la computer
after tiring of the by-hand approach.  FWIW, the by-hand approach reached:

The greedy algorithm can fail for {c,b,1} iff there are k and m satisfying:

        (m-1)*b/k < c <= m*(b-1)/k,	0 < k < m < b < c.