24 Oct 2013

Coin Change Problem

Problem Statement: 
               (Coin Change Problem)
Given coins V1 , V2 , V3 , .....Vn and amount W , find the minimum number of coins that sums to W.
Assume there are unlimited coins for each Vi    


V1
V2
V3
V4
V5
V6
1
3
6
12
24
30

W=53

Note : Unlimited number of coins for each coin value.

Solution : 

There is Greedy as well as dynamic approach for this , the shopkeeper uses Greedy Algorithm for large value of W, which may not be optimal at times.
          
Executing Greedy approach the result will be

1 x 30 + 1 x 12 + 1 x 6  +  1 x 3 + 2 x 1 = 53  ( 6 coins)

Whereas the optimal Solution using Dynamic Programming is  2 x 24 + 1 x 3 + 2 x 1= 53 (5 coins) 

I. Greedy Approach :
              Arrange the coins in reverse order , and if the coin value Vi  is lesser than W , subtract that value from from W ,

Algorithm:
  1.  Arrange Coins in reverse Order
  2.  If Coin value Vi  is lesser the W , subtract that Vi from W and print Vi, Else move to next coin value
  3.  Repeat step 2 until  W becomes 0 and all coins are traversed. 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
       /**
  * Pass the array in descending value
  * @param coins : value of coins
  * @param size : number of coins
  * @param W : change required for the amount
  */
 public static void greedyCoinChange(int coins[] , int size , int W ) {
  int i=0;
  while (W != 0 && i < size)  {

   if( coins[i] > W) i++;

   else {
    System.out.println(coins[i]);
    W = W - coins[i];
   }
  }
  
 }


II. Dynamic Programming

       Dynamic Programming is used where solutions of same problem is needed again and again.

             For the given problem to solve using dynamic programming we will have to develop an Optimal Sub structure as done in every dynamic problem , we need to ensure that solution to every sub-problem is optimal and combined result also produces optimal solution.
Every Dynamic Programming problem has the following properties:
a) Optimal Sub- Structure
b) Overlapping sub-problem

The given problem is optimal sub- problem as well , so we can use recursion as well to count the number of coins required. This problem can be solved with help of a beautiful equation below , and with the mighty power of recursion applied on the equation, therefore optimal equation is for the optimal sub-structure is :

     f  (W) =mini=1 to N     {  f (W – Vi ) }  + 1     for i=1....N    for all  Vi < W

where f  (W) is minimum number of coins required to make change for amount W.

Lets expand the above equation :
 f  (W) =mini=1 to N {  f (W – V1) ,  f (W – V2) , f (W – V3), .............f (W – VN) }  + 1

                                                                                      
Note:  f  (0) = 0 , i.e. number of coins required to change 0 is 0.

Now let us illustrate the above equation  with a smaller  data for the problem

 W = 5


V1
V2
V3
1
2
3
 
f  (1) = mini=1 to N   {  f  (1 - V1) } + 1  =  mini=1 to N   {  f  (0) } + 1  = 1
f  (2) = mini=1 to N   {  f  (2 - V1) ,f  (2 - V2) } + 1  
            =  mini=1 to N   {  (1) ,  (0) }  + 1

            =  min { 1 , 0 }  + 1 = 1
f  (3) = mini=1 to N   {  f  (3 - V1) ,f  (3 - V2) , f  (3 - V3) }  + 1 
             = mini=1 to N   {  f  (2) ,f  (1) , f  (0) }  + 1 

             = min { 1 , 1 ,  0 } + 1 = 1
f  (4) = mini=1 to N   {  f  (4 - V1) ,f  (4 - V2) , f  (4 - V3) }  + 1
            = mini=1 to N   {  f  (3) ,f  (2) , f  (1) }  + 1  

             = min { 1 , 1 ,  1 } + 1 =2
f  (5) = mini=1 to N   {  f  (5 - V1) ,f  (5- V2) , f  (5 - V3) }  + 1
            = mini=1 to N   {  f  (4) ,f  (3) , f  (2) }  + 1  
      
             = min { 1  , 1 , 1 } + 1 = 2

The Matrix representation of the values calculated.


V\W
0
1
2
3
4
5
0
0
1
1
1
-
 -
1
0
-
2
2
2
2
2
0
-
-
2
2
2
3
0
-
-
-
2
2

 The blue colored cell is minimum in the column for every value of 'w' till 'W'.

Algorithm :

Change(coins, W, size)
1 fValues[0] ← 0
2 for p ← 1 to W
3 min ← ∞
4        for i ← 1 to size
5                  if coins[i] ≤ p then
6                         if 1 + C[p − coins[i]] < min then
7                                  min ← 1 + C[p − coins[i]]
8                                  coin ← i
9                                  fValues[p] ← min
10                       S[p] ← coin
11 return C and S

Refer to full Source Code


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
        static int index=0;
 static int [] S = new int[W + 1];
 static int[] fValues= new int[W+1] ;

 public void coinChange(int[] coins , int w){

  if(w > W)
   return ;

  int min=w , fValue , coin = 0;
 
  for(int i=0;i<coins.length ;i++) {
   if(w >= coins[i]) {

    fValue = fValues[w-coins[i]] ;
    
    if(min > fValue)
    {
     min = fValue;
     coin=i;
    }
   }
  }
  fValues[++index] = min +1 ;
  
  S[w] = coin ;
  coinChange(coins , w + 1);
 }
 
 public void print(int W ){
  while(W>0)  {
   System.out.print(coins[S[W]] + "\t");
   W=W-coins[S[W]];
  }
 }

References: http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf

27 comments:

  1. Some birds, as an example will participate in singing displays that
    mirror the motions with the grass display like the Cutthroat finch.
    Or you might simply have information on a related
    field that your target audience would find interesting.
    Also, checking within the business running case can provide more details on whom to work with and
    whether you'll find discounts offered to participating businesses.



    Feel free to visit my site; trade show display
    units company ()

    ReplyDelete
  2. Some birds, as an example will engage in singing displays that mirror
    the motions with the grass display much like the Cutthroat finch.
    However, locking in rates early will help you secure the best selection and enable you to spread out expenditures over the greater span of time for max
    savings. Instead of relying upon your basic display to direct your visitors, you can think about
    using trade exhibition island booths for any more dramatic and effective directing force.


    Stop by my blog post; buy display board

    ReplyDelete
  3. These be able to hold 50% excess fat than a standard slatwall.
    To my mind there is nothing simpler or spontaneous than arranging fresh
    flowers in the vase. Three popular raffle drum trends that you have probably noticed in action are fabricated from either steel, clear acrylic,
    or another form of plastic generally known as PETG.


    my homepage - cheap banners trade show

    ReplyDelete
  4. From small, mom and pop shops all the way through to
    heavily established market leaders, each and every
    year businesses in every single industry in addition to every size choose to participate over these important promotional events.
    To my mind there is nothing more standard or spontaneous than arranging fresh flowers in a very vase.
    Also, checking within the business running the big
    event can provide additional information on whom to
    work with and whether you'll find discounts wanted to participating businesses.



    My web blog - custom trade show booth company

    ReplyDelete
  5. I am not sure where you're getting your info,
    but good topic. I needs to spend some time learning more or understanding more.
    Thanks for wonderful info I was looking for this information for my
    mission.

    Feel free to surf to my blog; online romance

    ReplyDelete
  6. Appreciating the dedication you put into your website and detailed information you provide.
    It's good to come across a blog every once in a
    while that isn't the same old rehashed information. Great read!

    I've saved your site and I'm including your RSS feeds to my Google account.


    my site :: karatbars international testimonies

    ReplyDelete
  7. It's really a nice and helpful piece of info. I'm glad that you just shared this useful information with us.
    Please keep us up to date like this. Thank you for sharing.



    Stop by my page :: karatbars reviews

    ReplyDelete
  8. I know this if off topic but I'm looking into
    starting my own weblog and was curious what all is required to get set up?

    I'm assuming having a blog like yours would
    cost a pretty penny? I'm not very internet smart so I'm not 100% positive.
    Any tips or advice would be greatly appreciated. Thanks

    Review my web page :: credit rebuilding credit cards

    ReplyDelete
  9. Thanks for sharing your thoughts on private jet charter broker.

    Regards

    Also visit my site; the price of a private jet

    ReplyDelete
  10. What i don't understood is actually how you're now not actually much more well-preferred than you might be right now.
    You're so intelligent. You recognize thus considerably in the case of this matter,
    produced me in my opinion consider it from numerous numerous angles.
    Its like men and women don't seem to be fascinated unless
    it is something to do with Woman gaga! Your own stuffs great.
    All the time maintain it up!

    my homepage :: private jet charter prices online

    ReplyDelete
  11. Excellent post. I used to be checking continuously
    this weblog and I am impressed! Extremely useful information particularly the last section :
    ) I handle such info a lot. I used to be seeking this particular information for a long time.
    Thanks and best of luck.

    Also visit my blog post :: anti wrinkle eye cream review

    ReplyDelete
  12. I amm sure this article has touchd alll the internet users, its really really pleasant article
    onn building up new weblog.

    my website ... Las Vegas Microwave Repair

    ReplyDelete
  13. What's up, just wanted to mention, I loved this article.
    It was funny. Keep on posting!

    Here is my page ... Las Vegas Kenmore Service

    ReplyDelete
  14. I think this is among the most important info for me.
    And i am glad reading your article. But should remark on few general
    things, The site style is great, the articles is really excellent : D.
    Good job, cheers

    my blog - cheap charter flights

    ReplyDelete
  15. Admiring the dedication you put into your website and in depth information you
    offer. It's good to come across a blog every once in a while that isn't the same out of date rehashed material.
    Excellent read! I've bookmarked your site and I'm including your RSS feeds to my Google account.


    Also visit my website - social media calendar template

    ReplyDelete
  16. Hey there! I just want to give you a big thumbs up for the great information you have got here on this post.
    I will be coming back to your site for more soon.

    my page :: internet marketing

    ReplyDelete
  17. Aw, this was a really nice post. Spending some time and actual
    effort to generate a good article… but what
    can I say… I procrastinate a lot and never manage to get anything done.


    Here is my blog post ... karatbars international official site

    ReplyDelete
  18. Hmm it appears like your site ate my first comment (it was super long) so
    I guess I'll just sum it up what I had written and
    say, I'm thoroughly enjoying your blog. I as
    well am an aspiring blog writer but I'm still
    new to everything. Do you have any helpful hints for beginner blog writers?
    I'd certainly appreciate it.

    Feel free to surf to my page; internet search engines

    ReplyDelete
  19. Asking questions are actually fastidious thing if you are not understanding something entirely,
    but this paragraph gives pleasant understanding yet.


    My weblog - work online

    ReplyDelete
  20. Nice post. I learn something totally new and challenging on blogs I stumbleupon on a daily basis.

    It's always useful to read through articles from other writers and practice something from other
    sites.

    my homepage - to sell my house

    ReplyDelete
  21. I am extremely impressed with your writing skills as well as with the layout on your blog.

    Is this a paid theme or did you customize it yourself?
    Anyway keep up the excellent quality writing,
    it's rare to see a nice blog like this one today.

    My page: karatbars candy crush gold bars what are they for

    ReplyDelete
  22. Great goods from you, man. I've understand your stuff previous to and you are just too excellent.
    I actually like what you have acquired here, really like what you're
    saying and the way in which you say it. You make it entertaining
    and you still take care of to keep it sensible.
    I can't wait to read much more from you. This is actually a
    great web site.

    Have a look at my web blog search engine optimization search engine optimization

    ReplyDelete
  23. hello there and thank you for your info – I've certainly
    picked up something new from right here.
    I did however expertise some technical points using this site, since I experienced
    to reload the site a lot of times previous to I could get it
    to load correctly. I had been wondering if your web host is OK?

    Not that I am complaining, but slow loading instances times
    will very frequently affect your placement in google and can damage your
    high quality score if advertising and marketing with Adwords.
    Well I'm adding this RSS to my e-mail and could look out for much
    more of your respective exciting content. Make sure you update this again very
    soon.

    Here is my site; karatbars international business cards

    ReplyDelete
  24. Tremendous issues here. I'm very glad to see your post.

    Thanks so much and I am having a look forward to touch you.
    Will you please drop me a mail?

    Feel free to surf to my blog - medical claims solicitors

    ReplyDelete