{"id":30,"date":"2020-05-06T16:22:32","date_gmt":"2020-05-06T16:22:32","guid":{"rendered":"http:\/\/sites.tntech.edu\/acrockett\/?p=30"},"modified":"2020-05-09T23:26:31","modified_gmt":"2020-05-09T23:26:31","slug":"change-making-dynamic-programming-algorithm","status":"publish","type":"post","link":"https:\/\/sites.tntech.edu\/acrockett\/2020\/05\/06\/change-making-dynamic-programming-algorithm\/","title":{"rendered":"Change Making Dynamic Programming Algorithm"},"content":{"rendered":"\n<p>Give change for amount (<strong><em>n<\/em><\/strong>) using the minimum number of coins of denominations (<strong><em>d1 &lt; d2 &lt; \u2026 &lt; dm<\/em><\/strong>).&nbsp;<\/p>\n\n\n\n<p>There is also a greedy algorithm to solve this problem but this post is on the dynamic programming technique algorithm.&nbsp;<\/p>\n\n\n\n<p>In this problem, we assume that there is an unlimited quantity of coins for each of the <strong><em>m<\/em><\/strong> denominations.&nbsp; In other words, we will never run out of change.<\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<h2 class=\"wp-block-heading\">Videos<\/h2>\n<\/div><\/div>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Change Making Dynamic Programming Algorithm\" width=\"1140\" height=\"855\" src=\"https:\/\/www.youtube.com\/embed\/VGloYuw9zuk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by April Crockett for Design of Algorithms in April 2020<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Change Making DP Algorithm\" width=\"1140\" height=\"641\" src=\"https:\/\/www.youtube.com\/embed\/L0RhpqqdXn4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by Mark Ralph for Design of Algorithms in May 2020<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Change Making DP Algorithm by Daniel Simpson\" width=\"1140\" height=\"641\" src=\"https:\/\/www.youtube.com\/embed\/JT-9hm67zQE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by Daniel Simpson for Design of Algorithms in April 2020<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"CSC 2400-001 Design of Algorithms: Change Making DP\" width=\"1140\" height=\"641\" src=\"https:\/\/www.youtube.com\/embed\/-sgdUCN5-Hw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by Alexander Clifford for Design of Algorithms in May 2020<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Algorithm Steps on Sample Input<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">Step One<\/h3>\n\n\n\n<p>Create an array of size amount +1.&nbsp; Four our example, the array would be 7 elements since the amount is 6.&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>F<\/td><td>0<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Step Two<\/h3>\n\n\n\n<p>Then, set F[0] to 0.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>F<\/td><td>0<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>0<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Step Three:&nbsp; (repetitive part)<\/h3>\n\n\n\n<p>Iterate through each index of the table using the formula F[i] = minimum of {F[i-1], F[i-3], F[i-4]} + 1<\/p>\n\n\n\n<p>i = 1<\/p>\n\n\n\n<p>F[1] = minimum{F[1-1]}+1 = 1<\/p>\n\n\n\n<p>Note that we do not worry about coin 3 or 4 when i is equal to one because 1 is smaller than coin 3 or 4.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>F<\/td><td>0<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>0<\/td><td>1<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>i=2<\/p>\n\n\n\n<p>F[2] = minimum{F[2-1]} + 1 = 2<\/p>\n\n\n\n<p>Again we didn\u2019t worry about coin 3 or 4 when i is equal to two because 2 is smaller than coin 3 or 4.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>F<\/td><td>0<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>0<\/td><td>1<\/td><td>2<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>i=3<\/p>\n\n\n\n<p>F[3] = minimum{F[3-1],F[3-3]}+1 = 1<\/p>\n\n\n\n<p>We didn\u2019t worry about coin 4 because when i is equal to 3 is smaller than coin 4.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>F<\/td><td>0<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>0<\/td><td>1<\/td><td>2<\/td><td>1<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>i=4<\/p>\n\n\n\n<p>F[4] = minimum{F[4-1],F[4-3],F[4-4]}+1 = 1<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>F<\/td><td>0<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>0<\/td><td>1<\/td><td>2<\/td><td>1<\/td><td>1<\/td><td>&nbsp;<\/td><td>&nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>i=5<\/p>\n\n\n\n<p>F[5] = minimum{F[5-1],F[5-3],F[5-4]}+1 = 2<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>F<\/td><td>0<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>0<\/td><td>1<\/td><td>2<\/td><td>1<\/td><td>1<\/td><td>2<\/td><td>&nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>i=6<\/p>\n\n\n\n<p>F[6] = minimum{F[6-1],F[6-3],F[6-4]}+1 = <strong>2<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>F<\/td><td>0<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>0<\/td><td>1<\/td><td>2<\/td><td>1<\/td><td>1<\/td><td>2<\/td><td>2<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Output<\/h3>\n\n\n\n<p>The algorithm returns F[6] as the output, which is 2.&nbsp; This is the least amount of coins that we can give as change with the given input is 2.<\/p>\n\n\n\n<p>Which coin produced the minimum value for i=6?&nbsp; It was coin 3.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Pseudocode<\/h2>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<pre class=\"wp-block-code\"><code>ALGORITHM ChangeMaking(D&#091;1..m],n)\n\/\/Input: Postitive integer na nd array D&#091;1..m] of increasing positive integers indicating the coin denominations where D&#091;1]=1\n\/\/Output: The minimum number of coins that add up to n\nF&#091;0] = 0;\nfor(i=1; i&lt;n; i++){\n\ttemp = infinity;\n\tj = 1;\n\twhile(j &lt;=m and i&gt;=D&#091;j]){\n\t\ttemp = min(F&#091;i-D&#091;j]],temp);\n\t\tj=j+1;\n\t}\n}\nreturn F&#091;n];\n<\/code><\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Time &amp; Space Efficiency<\/h2>\n\n\n\n<p>Time:  \u03f4(mn)<br>Space:  \u03f4(n)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Give change for amount (n) using the minimum number of coins of denominations (d1 &lt; d2 &lt; \u2026 &lt; dm).&nbsp; There is also a greedy algorithm to solve this problem but this post is on the dynamic programming technique algorithm.&nbsp; In this problem, we assume that there is an unlimited quantity of coins for each [&hellip;]<\/p>\n","protected":false},"author":119,"featured_media":34,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[4,3],"class_list":{"0":"post-30","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-algorithms","8":"tag-algorithms","9":"tag-dynamic-programming","10":"czr-hentry"},"_links":{"self":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts\/30","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/users\/119"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/comments?post=30"}],"version-history":[{"count":3,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts\/30\/revisions"}],"predecessor-version":[{"id":78,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts\/30\/revisions\/78"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/media\/34"}],"wp:attachment":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/media?parent=30"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/categories?post=30"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/tags?post=30"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}