**Problem Statement:**

**(Coin Change Problem)**

Given coins V

_{1 , }V

_{2}, V

_{3}, .....V

_{n }and amount W , find the minimum number of coins that sums to W.

Assume there are unlimited coins for each V

_{i }V_{1} |
V_{2} |
V_{3} |
V_{4} |
V_{5} |
V_{6} |

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

**V**is lesser than W , subtract that value from from W ,

_{i}**Algorithm:**

- Arrange Coins in reverse Order
- If Coin value
**V**is lesser the W , subtract that V_{i }_{i }from W and print V_{i}, Else move to next coin value - 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) =min

_{i=1 to N}{ f (W – V_{i}_{ }) } + 1 for i=1....N**for all V**_{i}< Wwhere f (W) is minimum number of coins required to make change for amount W.

Lets expand the above equation :

**f (W) =min**

_{i=1 to N}{ f (W – V

_{1}

_{}) , f (W – V

_{2}) , f (W – V

_{3}), .............f (W – V

_{N}) } + 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**

V_{1} |
V_{2} |
V_{3} |

1 |
2 |
3 |

f (1) = min

_{i=1 to N}{ f (1 - V

_{1}) } + 1 = min

_{i=1 to N}{ f (0) } + 1 = 1

f (2) = min

_{i=1 to N}{ f (2 - V

_{1}) ,f (2 - V

_{2}) } + 1

= min

_{i=1 to N}{ f (1) , f (0) } + 1

= min { 1 , 0 } + 1 = 1

f (3) = min

_{i=1 to N}{ f (3 - V

_{1}) ,f (3 - V

_{2}) , f (3 - V

_{3}) } + 1

= min

_{i=1 to N}{ f (2) ,f (1

_{}) , f (0

_{}) } + 1

= min { 1 , 1 , 0 } + 1 = 1

f (4) = min

_{i=1 to N}{ f (4 - V

_{1}) ,f (4 - V

_{2}) , f (4 - V

_{3}) } + 1

= min

_{i=1 to N}{ f (3

_{}) ,f (2

_{}) , f (1) } + 1

= min { 1 , 1 , 1 } + 1 =2

f (5) = min

= min

= min { 1 , 1 , 1 } + 1 = 2

The Matrix representation of the values calculated.

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

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

###

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

_{i=1 to N}{ f (5 - V_{1}) ,f (5- V_{2}) , f (5 - V_{3}) } + 1= min

_{i=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

Some birds, as an example will participate in singing displays that

ReplyDeletemirror 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 ()

Some birds, as an example will engage in singing displays that mirror

ReplyDeletethe 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

These be able to hold 50% excess fat than a standard slatwall.

ReplyDeleteTo 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

From small, mom and pop shops all the way through to

ReplyDeleteheavily 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

I am not sure where you're getting your info,

ReplyDeletebut 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

Appreciating the dedication you put into your website and detailed information you provide.

ReplyDeleteIt'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

It's really a nice and helpful piece of info. I'm glad that you just shared this useful information with us.

ReplyDeletePlease keep us up to date like this. Thank you for sharing.

Stop by my page :: karatbars reviews

I know this if off topic but I'm looking into

ReplyDeletestarting 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

Thanks for sharing your thoughts on private jet charter broker.

ReplyDeleteRegards

Also visit my site; the price of a private jet

What i don't understood is actually how you're now not actually much more well-preferred than you might be right now.

ReplyDeleteYou'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

Excellent post. I used to be checking continuously

ReplyDeletethis 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

I amm sure this article has touchd alll the internet users, its really really pleasant article

ReplyDeleteonn building up new weblog.

my website ... Las Vegas Microwave Repair

What's up, just wanted to mention, I loved this article.

ReplyDeleteIt was funny. Keep on posting!

Here is my page ... Las Vegas Kenmore Service

I think this is among the most important info for me.

ReplyDeleteAnd 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

Admiring the dedication you put into your website and in depth information you

ReplyDeleteoffer. 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

Hey there! I just want to give you a big thumbs up for the great information you have got here on this post.

ReplyDeleteI will be coming back to your site for more soon.

my page :: internet marketing

Aw, this was a really nice post. Spending some time and actual

ReplyDeleteeffort 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

Hmm it appears like your site ate my first comment (it was super long) so

ReplyDeleteI 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

Asking questions are actually fastidious thing if you are not understanding something entirely,

ReplyDeletebut this paragraph gives pleasant understanding yet.

My weblog - work online

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

ReplyDeleteIt's always useful to read through articles from other writers and practice something from other

sites.

my homepage - to sell my house

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

ReplyDeleteIs 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

Great goods from you, man. I've understand your stuff previous to and you are just too excellent.

ReplyDeleteI 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

hello there and thank you for your info – I've certainly

ReplyDeletepicked 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

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

ReplyDeleteThanks 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