{"id":26072,"date":"2017-10-26T19:46:57","date_gmt":"2017-10-26T14:16:57","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26072"},"modified":"2018-10-31T11:32:17","modified_gmt":"2018-10-31T06:02:17","slug":"python-programming-0-1-knapsack-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-0-1-knapsack-problem\/","title":{"rendered":"Python Programming &#8211; 0-1 Knapsack Problem"},"content":{"rendered":"<p><span style=\"color: #003366;\"><strong>0-1 Knapsack Problem:<\/strong><\/span><\/p>\n<p>Given weights and values of n items, put these items in a <a href=\"https:\/\/www.wikitechy.com\/technology\/branch-bound-implementation-01-knapsack\/\" target=\"_blank\" rel=\"noopener\">knapsack<\/a> of capacity W to get the maximum total value in the knapsack. <span id=\"more-18430\"><\/span>In other words, given two integer <a href=\"https:\/\/www.wikitechy.com\/tutorials\/python\/array-in-python\" target=\"_blank\" rel=\"noopener\">arrays<\/a> <strong>val[0..n-1] and wt[0..n-1]<\/strong> which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don\u2019t pick it (0-1 property).<\/p>\n<p>A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.<\/p>\n<h3 id=\"optimal-substructure\"><span style=\"color: #008080;\"><strong>Optimal Substructure:<\/strong><\/span><\/h3>\n<p>To consider all subsets of items, there can be two cases for every item: (1) the item is<strong> included<\/strong> in the optimal subset, (2) <strong>not included<\/strong> in the optimal set.<br \/>\nTherefore, the maximum value that can be obtained from n items is max of following two values.<\/p>\n<ul>\n<li>Maximum value obtained by <strong>n-1 items and W weight<\/strong> (excluding nth item).<\/li>\n<li>Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).<\/li>\n<\/ul>\n<p>If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.<\/p>\n<h3 id=\"overlapping-subproblems\"><span style=\"color: #008080;\"><strong>Overlapping Subproblems:<\/strong><\/span><\/h3>\n<p>Following is recursive implementation that simply follows the recursive structure mentioned above.<\/p>\n<h3 id=\"implementation-of-python\"><span style=\"color: #339966;\">Implementation of Python:<\/span><\/h3>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Python<\/span> <\/div> <pre class=\"language-python code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-python code-embed-code\">#A naive recursive implementation of 0-1 Knapsack Problem<br\/> <br\/># Returns the maximum value that can be put in a knapsack of<br\/># capacity W<br\/>def knapSack(W , wt , val , n):<br\/> <br\/>    # Base Case<br\/>    if n == 0 or W == 0 :<br\/>        return 0<br\/> <br\/>    # If weight of the nth item is more than Knapsack of capacity<br\/>    # W, then this item cannot be included in the optimal solution<br\/>    if (wt[n-1] &gt; W):<br\/>        return knapSack(W , wt , val , n-1)<br\/> <br\/>    # return the maximum of two cases:<br\/>    # (1) nth item included<br\/>    # (2) not included<br\/>    else:<br\/>        return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),<br\/>                   knapSack(W , wt , val , n-1))<br\/> <br\/># end of function knapSack<br\/> <br\/># To test above function<br\/>val = [60, 100, 120]<br\/>wt = [10, 20, 30]<br\/>W = 50<br\/>n = len(val)<br\/>print knapSack(W , wt , val , n)<\/code><\/pre> <\/div>\n<h3 id=\"output\"><span style=\"color: #008000;\">Output:<\/span><\/h3>\n<pre>220<\/pre>\n<p>It should be noted that the above function computes the same subproblems again and again. See the following recursion tree, K(1, 1) is being evaluated twice. <strong>Time complexity<\/strong> of this naive recursive solution is exponential <strong>(2^n).<\/strong><\/p>\n[ad type=&#8221;banner&#8221;]\n<pre>In the following recursion tree, K() refers to knapSack().  The two \r\nparameters indicated in the following recursion tree are n and W.  \r\nThe recursion tree is for following sample inputs.\r\nwt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}\r\n\r\n                       K(3, 2)         ---------&gt; K(n, W)\r\n                   \/            \\ \r\n                 \/                \\               \r\n            K(2,2)                  K(2,1)\r\n          \/       \\                  \/    \\ \r\n        \/           \\              \/        \\\r\n       K(1,2)      K(1,1)        K(1,1)     K(1,0)\r\n       \/  \\         \/   \\          \/   \\\r\n     \/      \\     \/       \\      \/       \\\r\nK(0,2)  K(0,1)  K(0,1)  K(0,0)  K(0,1)   K(0,0)\r\nRecursion tree for Knapsack capacity 2 units and 3 items of 1 unit weight.\r\n<\/pre>\n<p>Since subproblems are evaluated again, this problem has Overlapping Subprolems property. So the 0-1 Knapsack problem has both properties of a dynamic programming problem. Like other typical <a href=\"https:\/\/www.wikitechy.com\/technology\/variations-of-lis\/\" target=\"_blank\" rel=\"noopener\">Dynamic Programming<\/a>(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array K[][] in bottom up manner. Following is Dynamic Programming based implementation based <a href=\"https:\/\/www.wikitechy.com\/tutorials\/python\/running-python-programs\" target=\"_blank\" rel=\"noopener\">python<\/a>.<\/p>\n<h3 id=\"implementation-of-python-2\"><span style=\"color: #339966;\">Implementation of Python:<\/span><\/h3>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Python<\/span> <\/div> <pre class=\"language-python code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-python code-embed-code\"># A Dynamic Programming based Python Program for 0-1 Knapsack problem<br\/># Returns the maximum value that can be put in a knapsack of capacity W<br\/>def knapSack(W, wt, val, n):<br\/>    K = [[0 for x in range(W+1)] for x in range(n+1)]<br\/> <br\/>    # Build table K[][] in bottom up manner<br\/>    for i in range(n+1):<br\/>        for w in range(W+1):<br\/>            if i==0 or w==0:<br\/>                K[i][w] = 0<br\/>            elif wt[i-1] &lt;= w:<br\/>                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])<br\/>            else:<br\/>                K[i][w] = K[i-1][w]<br\/> <br\/>    return K[n][W]<br\/> <br\/># Driver program to test above function<br\/>val = [60, 100, 120]<br\/>wt = [10, 20, 30]<br\/>W = 50<br\/>n = len(val)<br\/>print(knapSack(W, wt, val, n))<\/code><\/pre> <\/div>\n<h3 id=\"output-2\"><span style=\"color: #339966;\">Output:<\/span><\/h3>\n<pre>220<\/pre>\n<p><span style=\"color: #808000;\"><strong>Time Complexity:<\/strong><\/span> <strong>O(nW)<\/strong> where n is the number of items and W is the capacity of knapsack.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Python Programming &#8211; 0-1 Knapsack Problem &#8211; Dynamic Programming simple solution is to consider all subsets of items and calculate the total weight and value<\/p>\n","protected":false},"author":1,"featured_media":31764,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,70145,4148],"tags":[76776,76782,76781,70610,76775,76799,70612,76796,76797,76780,72847,72842,72845,70483,72848,72840,75844,72846,72994,76772,76774,76786,72843,72992,72844,72850,72839,76783,76779,70580,76768,70579,76777,76798,76785,76784,71412,76770,70162,70605,76795,76769,70604,76787,76800,72852,72853,72851],"class_list":["post-26072","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-coding","category-dynamic-programming","category-python","tag-0-1-knapsack-dynamic-programming","tag-0-1-knapsack-problem-algorithm-in-dynamic-programming","tag-0-1-knapsack-problem-dynamic-programming-algorithm","tag-0-1-knapsack-problem-using-dynamic-programming","tag-0-1-knapsack-problem-using-dynamic-programming-algorithm","tag-0-1-knapsack-problem-using-dynamic-programming-code-python","tag-0-1-knapsack-problem-using-dynamic-programming-example","tag-0-1-knapsack-problem-using-dynamic-programming-in-python","tag-0-1-knapsack-problem-using-dynamic-programming-python-code","tag-0-1-knapsack-using-dynamic-programming","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-examples","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-python","tag-dynamic-programming-knapsack","tag-dynamic-programming-knapsack-problem","tag-dynamic-programming-knapsack-problem-example","tag-dynamic-programming-problems","tag-dynamic-programming-python","tag-dynamic-programming-software","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-implement-0-1-knapsack-problem-using-dynamic-programming","tag-knapsack-algorithm-dynamic-programming","tag-knapsack-dynamic-programming","tag-knapsack-problem-c","tag-knapsack-problem-dynamic-programming","tag-knapsack-problem-dynamic-programming-example","tag-knapsack-problem-dynamic-programming-python-code","tag-knapsack-problem-dynamic-programming-solution","tag-knapsack-problem-example-using-dynamic-programming","tag-knapsack-problem-example-using-greedy-method","tag-knapsack-problem-explained","tag-knapsack-problem-greedy-algorithm","tag-knapsack-problem-in-c","tag-knapsack-problem-in-python","tag-knapsack-problem-java","tag-knapsack-problem-using-dynamic-programming","tag-knapsack-problem-using-dynamic-programming-example","tag-knapsack-problem-using-dynamic-programming-python-code","tag-problems-on-dynamic-programming","tag-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26072","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=26072"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26072\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31764"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26072"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26072"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26072"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}