{"id":26669,"date":"2017-12-22T19:36:54","date_gmt":"2017-12-22T14:06:54","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26669"},"modified":"2017-12-22T19:36:54","modified_gmt":"2017-12-22T14:06:54","slug":"branch-bound-implementation-01-knapsack","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/branch-bound-implementation-01-knapsack\/","title":{"rendered":"Branch and Bound | Set 2 (Implementation of 0\/1 Knapsack)"},"content":{"rendered":"<p>We discussed different approaches to solve above problem and saw that the Branch and Bound solution is the best suited method when item weights are not integers.<\/p>\n<p>In this post implementation of Branch and Bound method for 0\/1 knapsack problem is discussed.<\/p>\n<p><strong>How to find bound for every node for 0\/1 Knapsack? <\/strong><br \/>\nThe idea is to use the fact that the <a href=\"http:\/\/www.geeksforgeeks.org\/fractional-knapsack-problem\/\" target=\"_blank\" rel=\"noopener\">Greedy approach<\/a> provides the best solution for Fractional Knapsack problem.<br \/>\nTo check if a particular node can give us a better solution or not, we compute the optimal solution (through the node) using Greedy approach. If the solution computed by Greedy approach itself is more than the best so far, then we can\u2019t get a better solution through the node.<\/p>\n<p><strong>Complete Algorithm:<\/strong><\/p>\n<ol>\n<li>Sort all items in decreasing order of ratio of value per unit weight so that an upper bound can be computed using Greedy Approach.<\/li>\n<li>Initialize maximum profit, maxProfit = 0<\/li>\n<li>Create an empty queue, Q.<\/li>\n<li>Create a dummy node of decision tree and enqueue it to Q. Profit and weight of dummy node are 0.<\/li>\n<li>Do following while Q is not empty.\n<ul>\n<li>Extract an item from Q. Let the extracted item be u.<\/li>\n<li>Compute profit of next level node. If the profit is more than maxProfit, then update maxProfit.<\/li>\n<li>Compute bound of next level node. If bound is more than maxProfit, then add next level node to Q.<\/li>\n<li>Consider the case when next level node is not considered as part of solution and add a node to queue with level as next, but weight and profit without considering next level nodes.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n[ad type=&#8221;banner&#8221;]\n<p><strong>Illustration<\/strong>:<\/p>\n<pre>Input:\r\n\/\/ First thing in every pair is weight of item\r\n\/\/ and second thing is value of item\r\nItem arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},\r\n              {5, 95}, {3, 30}};\r\nKnapsack Capacity W = 10\r\n\r\nOutput:\r\nThe maximum possible profit = 235\r\n\r\nBelow diagram shows illustration. Items are \r\nconsidered sorted by value\/weight.\r\n<a href=\"http:\/\/www.geeksforgeeks.org\/wp-content\/uploads\/branchandbound.png\" target=\"_blank\" rel=\"noopener\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone size-full wp-image-137651\" src=\"http:\/\/www.geeksforgeeks.org\/wp-content\/uploads\/branchandbound.png\" alt=\"branchandbound\" width=\"393\" height=\"283\" \/><\/a>\r\n\r\n<strong>Note : <\/strong> The image doesn't strictly follow the \r\nalgorithm\/code as there is no dummy node in the\r\nimage.\r\n\r\nThis image is adopted from <a href=\"http:\/\/www.cse.msu.edu\/~torng\/Classes\/Archives\/cse830.03fall\/Lectures\/Lecture11.ppt\" target=\"_blank\" rel=\"noopener\">here<\/a>.\r\n\r\n\r\n<\/pre>\n<p>Following is C++ implementation of above idea.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-cpp code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-cpp code-embed-code\">\/\/ C++ program to solve knapsack problem using<br\/>\/\/ branch and bound<br\/>#include &lt;bits\/stdc++.h&gt;<br\/>using namespace std;<br\/> <br\/>\/\/ Stucture for Item which store weight and corresponding<br\/>\/\/ value of Item<br\/>struct Item<br\/>{<br\/>    float weight;<br\/>    int value;<br\/>};<br\/> <br\/>\/\/ Node structure to store information of decision<br\/>\/\/ tree<br\/>struct Node<br\/>{<br\/>    \/\/ level  --&gt; Level of node in decision tree (or index<br\/>    \/\/             in arr[]<br\/>    \/\/ profit --&gt; Profit of nodes on path from root to this<br\/>    \/\/            node (including this node)<br\/>    \/\/ bound ---&gt; Upper bound of maximum profit in subtree<br\/>    \/\/            of this node\/<br\/>    int level, profit, bound;<br\/>    float weight;<br\/>};<br\/> <br\/>\/\/ Comparison function to sort Item according to<br\/>\/\/ val\/weight ratio<br\/>bool cmp(Item a, Item b)<br\/>{<br\/>    double r1 = (double)a.value \/ a.weight;<br\/>    double r2 = (double)b.value \/ b.weight;<br\/>    return r1 &gt; r2;<br\/>}<br\/> <br\/>\/\/ Returns bound of profit in subtree rooted with u.<br\/>\/\/ This function mainly uses Greedy solution to find<br\/>\/\/ an upper bound on maximum profit.<br\/>int bound(Node u, int n, int W, Item arr[])<br\/>{<br\/>    \/\/ if weight overcomes the knapsack capacity, return<br\/>    \/\/ 0 as expected bound<br\/>    if (u.weight &gt;= W)<br\/>        return 0;<br\/> <br\/>    \/\/ initialize bound on profit by current profit<br\/>    int profit_bound = u.profit;<br\/> <br\/>    \/\/ start including items from index 1 more to current<br\/>    \/\/ item index<br\/>    int j = u.level + 1;<br\/>    int totweight = u.weight;<br\/> <br\/>    \/\/ checking index condition and knapsack capacity<br\/>    \/\/ condition<br\/>    while ((j &lt; n) &amp;&amp; (totweight + arr[j].weight &lt;= W))<br\/>    {<br\/>        totweight    += arr[j].weight;<br\/>        profit_bound += arr[j].value;<br\/>        j++;<br\/>    }<br\/> <br\/>    \/\/ If k is not n, include last item partially for<br\/>    \/\/ upper bound on profit<br\/>    if (j &lt; n)<br\/>        profit_bound += (W - totweight) * arr[j].value \/<br\/>                                         arr[j].weight;<br\/> <br\/>    return profit_bound;<br\/>}<br\/> <br\/>\/\/ Returns maximum profit we can get with capacity W<br\/>int knapsack(int W, Item arr[], int n)<br\/>{<br\/>    \/\/ sorting Item on basis of value per unit<br\/>    \/\/ weight.<br\/>    sort(arr, arr + n, cmp);<br\/> <br\/>    \/\/ make a queue for traversing the node<br\/>    queue&lt;Node&gt; Q;<br\/>    Node u, v;<br\/> <br\/>    \/\/ dummy node at starting<br\/>    u.level = -1;<br\/>    u.profit = u.weight = 0;<br\/>    Q.push(u);<br\/> <br\/>    \/\/ One by one extract an item from decision tree<br\/>    \/\/ compute profit of all children of extracted item<br\/>    \/\/ and keep saving maxProfit<br\/>    int maxProfit = 0;<br\/>    while (!Q.empty())<br\/>    {<br\/>        \/\/ Dequeue a node<br\/>        u = Q.front();<br\/>        Q.pop();<br\/> <br\/>        \/\/ If it is starting node, assign level 0<br\/>        if (u.level == -1)<br\/>            v.level = 0;<br\/> <br\/>        \/\/ If there is nothing on next level<br\/>        if (u.level == n-1)<br\/>            continue;<br\/> <br\/>        \/\/ Else if not last node, then increment level,<br\/>        \/\/ and compute profit of children nodes.<br\/>        v.level = u.level + 1;<br\/> <br\/>        \/\/ Taking current level&#039;s item add current<br\/>        \/\/ level&#039;s weight and value to node u&#039;s<br\/>        \/\/ weight and value<br\/>        v.weight = u.weight + arr[v.level].weight;<br\/>        v.profit = u.profit + arr[v.level].value;<br\/> <br\/>        \/\/ If cumulated weight is less than W and<br\/>        \/\/ profit is greater than previous profit,<br\/>        \/\/ update maxprofit<br\/>        if (v.weight &lt;= W &amp;&amp; v.profit &gt; maxProfit)<br\/>            maxProfit = v.profit;<br\/> <br\/>        \/\/ Get the upper bound on profit to decide<br\/>        \/\/ whether to add v to Q or not.<br\/>        v.bound = bound(v, n, W, arr);<br\/> <br\/>        \/\/ If bound value is greater than profit,<br\/>        \/\/ then only push into queue for further<br\/>        \/\/ consideration<br\/>        if (v.bound &gt; maxProfit)<br\/>            Q.push(v);<br\/> <br\/>        \/\/ Do the same thing,  but Without taking<br\/>        \/\/ the item in knapsack<br\/>        v.weight = u.weight;<br\/>        v.profit = u.profit;<br\/>        v.bound = bound(v, n, W, arr);<br\/>        if (v.bound &gt; maxProfit)<br\/>            Q.push(v);<br\/>    }<br\/> <br\/>    return maxProfit;<br\/>}<br\/> <br\/>\/\/ driver program to test above function<br\/>int main()<br\/>{<br\/>    int W = 10;   \/\/ Weight of knapsack<br\/>    Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},<br\/>                  {5, 95}, {3, 30}};<br\/>    int n = sizeof(arr) \/ sizeof(arr[0]);<br\/> <br\/>    cout &lt;&lt; &quot;Maximum possible profit = &quot;<br\/>         &lt;&lt; knapsack(W, arr, n);<br\/> <br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p>&nbsp;<\/p>\n<p>Output :<\/p>\n<pre>Maximum possible profit = 235<\/pre>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Branch and Bound (Implementation of 0\/1 Knapsack)-Branch and Bound The idea is to use the fact that the Greedy approach provides the best solution.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,79474,83613],"tags":[79596,79594,79593,79595,79597,79601,79598,79609,79599,79608,79600],"class_list":["post-26669","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-branch-and-bound","category-knapsack-problem","tag-0-1-knapsack-problem-using-branch-and-bound-c-code","tag-0-1-knapsack-problem-using-branch-and-bound-code","tag-0-1-knapsack-problem-using-branch-and-bound-example","tag-01-knapsack-problem-using-branch-and-bound-ppt","tag-01-knapsack-problem-using-least-cost-branch-and-bound","tag-01-knapsack-using-branch-and-bound","tag-branch-and-bound-algorithm-tutorial","tag-branch-and-bound-knapsack-problem-c","tag-branch-and-bound-travelling-salesman","tag-implementation-of-0-1-knapsack-problem-using-branch-and-bound-approach","tag-time-complexity-of-01-knapsack-using-branch-and-bound"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26669","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=26669"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26669\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26669"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26669"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26669"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}