{"id":25120,"date":"2017-10-15T14:35:14","date_gmt":"2017-10-15T09:05:14","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25120"},"modified":"2017-10-15T14:35:14","modified_gmt":"2017-10-15T09:05:14","slug":"greedy-algorithm-find-minimum-number-coins","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/greedy-algorithm-find-minimum-number-coins\/","title":{"rendered":"Greedy Algorithm to find Minimum number of Coins"},"content":{"rendered":"<p>Given a value V, if we want to make change for V Rs, and we have infinite supply of each of the denominations in Indian currency, i.e., we have infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins\/notes, what is the minimum number of coins and\/or notes needed to make the change?<span id=\"more-142580\"><\/span><\/p>\n<p>Examples:<\/p>\n<pre>Input: V = 70\r\nOutput: 2\r\nWe need a 50 Rs note and a 20 Rs note.\r\n\r\nInput: V = 121\r\nOutput: 3\r\nWe need a 100 Rs note, a 20 Rs note and a \r\n1 Rs coin.<\/pre>\n<div id=\"practice\">\n<h4 id=\"recommended-please-solve-it-on-practice-first-before-moving-on-to-the-solution\">Recommended: Please solve it on \u201c<b><u>PRACTICE<\/u><\/b>\u201d first, before moving on to the solution.<\/h4>\n<\/div>\n[ad type=\u201dbanner\u201d]\n<p>The idea is simple Greedy Algorithm. Start from largest possible denomination and keep adding denominations while remaining value is greater than 0. Below is complete algorithm.<\/p>\n<pre>1) Initialize result as empty.\r\n2) find the largest denomination that is \r\n   smaller than V.\r\n3) Add found denomination to result. Subtract \r\n   value of found denomination from V.\r\n4) If V becomes 0, then print result.  \r\n   Else repeat steps 2 and 3 for new value of V<\/pre>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20minimum%20number%20of%20denominations%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20All%20denominations%20of%20Indian%20Currency%0Aint%20deno%5B%5D%20%3D%20%7B1%2C%202%2C%205%2C%2010%2C%2020%2C%2050%2C%20100%2C%20500%2C%201000%7D%3B%0Aint%20n%20%3D%20sizeof(deno)%2Fsizeof(deno%5B0%5D)%3B%0A%20%0A%2F%2F%20Driver%20program%0Avoid%20findMin(int%20V)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20result%0A%20%20%20%20vector%3Cint%3E%20ans%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20through%20all%20denomination%0A%20%20%20%20for%20(int%20i%3Dn-1%3B%20i%3E%3D0%3B%20i\u2013)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20denominations%0A%20%20%20%20%20%20%20%20while%20(V%20%3E%3D%20deno%5Bi%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20V%20-%3D%20deno%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20ans.push_back(deno%5Bi%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20result%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20ans.size()%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20ans%5Bi%5D%20%3C%3C%20%22%20%20%22%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%0Aint%20main()%0A%7B%0A%20%20%20int%20n%20%3D%2093%3B%0A%20%20%20cout%20%3C%3C%20%22Following%20is%20minimal%20number%20of%20change%20for%20%22%20%3C%3C%20n%20%3C%3C%20%22%20is%20%22%3B%0A%20%20%20findMin(n)%3B%0A%20%20%20return%200%3B%0A%7D%0A\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h4 id=\"output\"><strong>output:<\/strong><\/h4>\n<pre>Following is minimal number of change for 93 is 50  20  20  2  1<\/pre>\n<p>Note that above approach may not work for all denominations. For example, it doesn\u2019t work for denominations {9, 6, 5, 1} and V = 11. The above approach would print 9, 1 and 1. But we can use 2 denominations 5 and 6.<br \/>\nFor general input, we use below dynamic programming approach.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Greedy Algorithm to find Minimum number of Coins &#8211; Greedy Algorithm &#8211; Given a value V, if we want to make change for V Rs. and we have infinite supply of each of the denominations in Indian currency.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70144],"tags":[71506,71531,71544,71525,71512,71507,71508,71498,70151,71502,71516,71524,71547,71511,71513,71519,71518,71522,71534,71542,70175,71528,71509,71496,71503,71521,71505,71523,70147,71536,71495,71530,71541,71538,71497,71517,70152,70149,71545,71515,71520,71543,71529,71539,71546,71501,71532,71500,71514,71533,71510,71535,71540,71445,71527,71537,71526,71504,71499],"class_list":["post-25120","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-greedy-algorithm","tag-25-cent-coin-value","tag-activity-selection-problem-using-greedy-algorithm-example","tag-application-of-greedy-algorithm","tag-change-coins","tag-change-maker-machine","tag-change-making-problem-java","tag-changemaking","tag-characteristics-of-algorithm","tag-characteristics-of-greedy-algorithm","tag-coin-algorithm","tag-coin-amounts","tag-coin-change","tag-coin-change-problem-using-greedy-algorithm-in-c","tag-coin-changer","tag-coin-changing-algorithm","tag-coin-counting-problem","tag-coin-denominations","tag-coin-making","tag-coin-problems-with-solutions","tag-define-greedy-algorithm","tag-define-greedy-method","tag-denomination-examples","tag-dynamic-coin","tag-dynamic-programming-algorithm","tag-dynamic-programming-explained","tag-dynamic-programming-practice","tag-dynamic-programming-problems-and-solutions","tag-dynamic-programming-table","tag-greedy-algorithm","tag-greedy-algorithm-c","tag-greedy-algorithm-example","tag-greedy-algorithm-examples-pdf","tag-greedy-algorithm-in-c","tag-greedy-algorithm-knapsack-problem-with-example","tag-greedy-algorithm-problems-and-solutions","tag-greedy-algorithm-program-in-c","tag-greedy-algorithm-tutorial","tag-greedy-method","tag-greedy-problems","tag-greedy-program-in-c","tag-how-to-solve-coin-problems","tag-how-to-solve-knapsack-problem-using-greedy-method-example","tag-java-dynamic-programming","tag-knapsack-problem-greedy-algorithm-example","tag-knapsack-problem-greedy-algorithm-explanation","tag-leboncoin","tag-make-a-change","tag-make-algorithm","tag-make-it-change","tag-make-the-change","tag-math-making-change","tag-mcoins","tag-money-changing-problem","tag-pseudo-code-for-greedy-algorithm","tag-quarter-dime-nickel-penny","tag-understanding-dynamic-programming","tag-us-coin-denominations","tag-what-is-dynamic-programming","tag-what-is-the-meaning-of-greedy"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25120","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25120"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25120\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25120"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25120"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}