A friend of mine says that with the cash box given he can prove that
the greedy approach always works EXCEPT that if the greedy algorithm
would select an ODD number N of 500's, 50's 5's, or 0.25s, then the
algorithm must also try N-1 of the same denomination. This is because
they are congruent
Yes, you are right but this is not an efficient solution. It runs in
O(n*S) time and S in my case is sufficiently large.
What I have noticed that the greedy algorithm works indeed in most of
the cases. If there is at least one single number of each denomination,
the greedy algorithm will work
Your algorithm does not show how to select di. If you pick the
smallest possible denomination first, then consider S=6 with a cash box
of
2 x 1
1 x 5
The algorithm will pick both 1's and then fail because all that's left
is the 5.
If you pick the largest possble di then try S=60 with a cash box
oops.. 500,200 and 50,20 are values in the table.
so the algo doesnt work for this case
Indeed di-1 mod di = 0 is sufficient to make the greedy algorithm work,
but 50 mod 20 = 10!
This can be solved by Dynamic Programming.
Let the denominations be d1,d2,...,dn and their corresponding numbers
be P1,P2,...,Pn. Let C(n,S) be the matrix which tells us if the amount
S can be obtained by using coins d1,...,dn.
Then C(n,S) = C(n-1,S) if denomination dn is not used, else
C(n,S) =
