wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> coins and change
        
(Message started by: birbal on Feb 5^th, 2012, 9:07am)

Title: coins and change
Post by birbal on Feb 5^th, 2012, 9:07am

You have coins with different denominations and you have limited number of each denominations (some maybe zero), how will you determine if you can supply the given change.

Title: Re: coins and change
Post by towr on Feb 5^th, 2012, 11:23am

I think it depends on the denominations whether a greedy approach will work; but that'd be one thing to try.

Title: Re: coins and change
Post by R on Sep 22^nd, 2012, 2:50am

Can we model it as DP?

Title: Re: coins and change
Post by MathsForFun on Jul 20^th, 2013, 1:07am

on 09/22/12 at 02:50:19, R wrote:

Can we model it as DP?

Dynamic programming would be awkward in this case, because there would be multiple ways of getting to each amount.

I would use an integer programming library: unless the problem was extraordinarily large, it would answer this question in a snap.

http://en.wikipedia.org/wiki/Change-making_problem