{"id":50,"date":"2020-05-07T21:08:25","date_gmt":"2020-05-07T21:08:25","guid":{"rendered":"http:\/\/sites.tntech.edu\/acrockett\/?p=50"},"modified":"2024-10-30T20:11:42","modified_gmt":"2024-10-30T20:11:42","slug":"knapsack-dynamic-programming-algorithm","status":"publish","type":"post","link":"https:\/\/sites.tntech.edu\/acrockett\/2020\/05\/07\/knapsack-dynamic-programming-algorithm\/","title":{"rendered":"Knapsack Dynamic Programming Algorithm"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Problem Description<\/h2>\n\n\n\n<p>Given n items of known weights (w1,\u2026.,wn) and values (v1,\u2026,vn) and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.<\/p>\n\n\n\n<p>The 0-1 Knapsack Problem can be solved using the brute-force exhaustive search technique where you must find all 2n combinations.  However, using Dynamic Programming is much more efficient!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Videos<\/h2>\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=\"Knapsack DP Algorithm\" width=\"1140\" height=\"855\" src=\"https:\/\/www.youtube.com\/embed\/ev0UjhpeaDE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><\/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-002 Exam 3 Zthreet\" width=\"1140\" height=\"641\" src=\"https:\/\/www.youtube.com\/embed\/OGn_dFrhKgg?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by Zachariah Threet 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=\"Knapsack Dynamic Programming Algorithm\" width=\"1140\" height=\"641\" src=\"https:\/\/www.youtube.com\/embed\/tmd-HjYgLUU?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by Joshua Adams 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=\"2400 Final Exam, Jordan Myers\" width=\"1140\" height=\"641\" src=\"https:\/\/www.youtube.com\/embed\/OffzLOJL-4M?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by Jordan Myers for Design of Algorithms in May 2020<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Algorithm Steps Explained with Given Input<\/h2>\n\n\n\n<p>The knapsack has a total weight capacity (W) of 10 pounds.<\/p>\n\n\n\n<p>There are five items that I would like to put in my knapsack, but if I include them all, I would exceed the weight limit.<\/p>\n\n\n\n<p>The items are described below:<\/p>\n\n\n\n<ol class=\"wp-block-list\" type=\"1\"><li>Item 1 is a tennis shoe.&nbsp; It weighs 1 pound and has a value of $5.00<\/li><li>Item 2 is a pineapple.&nbsp; It weighs 2 pounds and has a value of $3.00<\/li><li>Item 3 is a toaster.&nbsp; It weighs 4 pounds and has a value of $5.00<\/li><li>Item 4 is a rack of baby back ribs.&nbsp; It weighs 2 pounds and has a value of $3.00<\/li><li>Item 5 is a 2 liter bottle of mountain dew.&nbsp; It weighs 5 pounds and has a value of $2.00<\/li><\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Step 1: Set up the Memoized Table<\/h3>\n\n\n\n<p>With the dynamic programming algorithm, we will memoize (or save) intermediate results in a table, which I demonstrate as a two-dimensional array in the table below.&nbsp; The name of the table is F.&nbsp; The table will have W+1 columns, where W is the weight capacity of the knapsack.&nbsp; So that means there will be 11 columns.&nbsp; The table will have n+1 rows, where n is the number of items.&nbsp; So that means there will be 6 rows.&nbsp; I will label each of the columns in the column header with an index value of the columns and I will label each of the rows in the row header with an index value of the rows.&nbsp; This will add an additional row &amp; column to the table below.<\/p>\n\n\n\n<p>Below is the initial table, with step 1 already done, which is to initialize all elements to zero.&nbsp; I will be using j to indicate the index value of the column, which represents the weight\/capacity of the knapsack and using i to indicate the index value of the row, which represents the item.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>&nbsp;<\/strong><\/td><td><strong>0 pounds<\/strong><\/td><td><strong>1 pound<\/strong><\/td><td><strong>2 pounds<\/strong><\/td><td><strong>3 pounds<\/strong><\/td><td><strong>4 pounds<\/strong><\/td><td><strong>5 pounds<\/strong><\/td><td><strong>6 pounds<\/strong><\/td><td><strong>7 pounds<\/strong><\/td><td><strong>8 pounds<\/strong><\/td><td><strong>9&nbsp; pounds<\/strong><\/td><td><strong>10 pounds<\/strong><\/td><\/tr><tr><td><strong>0<\/strong><\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><\/tr><tr><td><strong>item 1<\/strong><\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><\/tr><tr><td><strong>item 2<\/strong><\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><\/tr><tr><td><strong>item 3<\/strong><\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><\/tr><tr><td><strong>item 4<\/strong><\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><\/tr><tr><td><strong>item 5<\/strong><\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Step 2: Repeating Part of the Algorithm until we have a Solution<\/h3>\n\n\n\n<p>For each element in the table starting with i=1 and j=1, we will select the value based on a condition.&nbsp; In the calculations listed below, wi is the weight of the item at index i and vi is value of the item at index i.<\/p>\n\n\n\n<p>If (j-wi &gt;= 0) then F[i][j]=max{F[i-1][j] or vi+F[i-1][j-wi]<\/p>\n\n\n\n<p>If(j-wi &lt; 0) then F[i][j] = F[i-1][j]<\/p>\n\n\n\n<p>So, for example, at i=1 and j=1, the weight of item 1 is 1 pound and the value is $5.00.&nbsp; So, j-wi is 1-1, which is 0.&nbsp; So that means F[1][1] = max{F[0][1] or 5+F[0][0]}.&nbsp; 5+F[0][0] is 5 and so F[1][1] will be assigned 5.<\/p>\n\n\n\n<p>You would go through each row and each column in a nested loop and do these same steps until every element in F has a value.&nbsp; The resulting table is below.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>&nbsp;<\/strong><\/td><td><strong>0 pounds<\/strong><\/td><td><strong>1 pound<\/strong><\/td><td><strong>2 pounds<\/strong><\/td><td><strong>3 pounds<\/strong><\/td><td><strong>4 pounds<\/strong><\/td><td><strong>5 pounds<\/strong><\/td><td><strong>6 pounds<\/strong><\/td><td><strong>7 pounds<\/strong><\/td><td><strong>8 pounds<\/strong><\/td><td><strong>9&nbsp; pounds<\/strong><\/td><td><strong>10 pounds<\/strong><\/td><\/tr><tr><td><strong>0<\/strong><\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><td>0<\/td><\/tr><tr><td><strong>item 1<\/strong><\/td><td>0<\/td><td>5<\/td><td>5<\/td><td>5<\/td><td>5<\/td><td>5<\/td><td>5<\/td><td>5<\/td><td>5<\/td><td>5<\/td><td>5<\/td><\/tr><tr><td><strong>item 2<\/strong><\/td><td>0<\/td><td>5<\/td><td>5<\/td><td>8<\/td><td>8<\/td><td>8<\/td><td>8<\/td><td>8<\/td><td>8<\/td><td>8<\/td><td>8<\/td><\/tr><tr><td><strong>item 3<\/strong><\/td><td>0<\/td><td>5<\/td><td>5<\/td><td>8<\/td><td>8<\/td><td>10<\/td><td>10<\/td><td>13<\/td><td>13<\/td><td>13<\/td><td>13<\/td><\/tr><tr><td><strong>item 4<\/strong><\/td><td>0<\/td><td>5<\/td><td>5<\/td><td>8<\/td><td>8<\/td><td>11<\/td><td>11<\/td><td>13<\/td><td>13<\/td><td>16<\/td><td>16<\/td><\/tr><tr><td><strong>item 5<\/strong><\/td><td>0<\/td><td>5<\/td><td>5<\/td><td>8<\/td><td>8<\/td><td>11<\/td><td>11<\/td><td>13<\/td><td>13<\/td><td>16<\/td><td>16<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Output<\/h3>\n\n\n\n<p>The output of this algorithm is F[i][j], which in my example is F[5][10], which is 16.&nbsp; This means that the maximum value that we can fill our knapsack with is $16.00 when it has a weight limit or capacity of 10 pounds and with the five items described.&nbsp;<\/p>\n\n\n\n<p>One neat thing is that we can find out the maximum value we could have at all weight limits between 0 pounds and 10 pounds with this table.&nbsp; For example, in the column with 7 pounds, the largest value is 13, which means $13 is the highest value we can have if the weight limit were only 7 pounds.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Complexity\/Efficiency of the DP Algorithm<\/h2>\n\n\n\n<p>Time Efficiency is O(nW).<\/p>\n\n\n\n<p>Complexity does not contradict the fact that the knapsack problem is NP-complete, since W, unlike n, is not polynomial in the length of the input to the problem.&nbsp; The length of the W input to the problem is proportional to the number of bits in W, log W, not to W itself.&nbsp; However, since this runtime is pseudo polynomial, this makes the knapsack problem a weakly NP-complete problem.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Other Resources<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>GeeksforGeeks 0-1 Knapsack Problem | DP-10:  <a href=\"https:\/\/www.geeksforgeeks.org\/0-1-knapsack-problem-dp-10\/\">https:\/\/www.geeksforgeeks.org\/0-1-knapsack-problem-dp-10\/<\/a><\/li><li>Medium &#8211; How to solve the Knapsack Problem with dynamic programming: <a href=\"https:\/\/medium.com\/@fabianterh\/how-to-solve-the-knapsack-problem-with-dynamic-programming-eb88c706d3cf\">https:\/\/medium.com\/@fabianterh\/how-to-solve-the-knapsack-problem-with-dynamic-programming-eb88c706d3cf<\/a><\/li><li>Educative: <a href=\"https:\/\/www.educative.io\/courses\/grokking-dynamic-programming-patterns-for-coding-interviews\/RM1BDv71V60\">https:\/\/www.educative.io\/courses\/grokking-dynamic-programming-patterns-for-coding-interviews\/RM1BDv71V60<\/a><\/li><\/ul>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Description Given n items of known weights (w1,\u2026.,wn) and values (v1,\u2026,vn) and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack. The 0-1 Knapsack Problem can be solved using the brute-force exhaustive search technique where you must find all 2n combinations. However, using Dynamic Programming [&hellip;]<\/p>\n","protected":false},"author":119,"featured_media":57,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[4,3],"class_list":{"0":"post-50","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\/50","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=50"}],"version-history":[{"count":4,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts\/50\/revisions"}],"predecessor-version":[{"id":157,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts\/50\/revisions\/157"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/media\/57"}],"wp:attachment":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/media?parent=50"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/categories?post=50"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/tags?post=50"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}