{"id":2657,"date":"2021-10-13T19:20:00","date_gmt":"2021-10-13T13:50:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2657"},"modified":"2021-10-13T17:31:20","modified_gmt":"2021-10-13T12:01:20","slug":"fractional-knapsack-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/fractional-knapsack-problem\/","title":{"rendered":"Fractional Knapsack Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#brute-force-approach\">Brute Force Approach<\/a><\/li><li><a href=\"#efficient-approachgreedy\">Efficient Approach(Greedy)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java--implementation\">Java <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#python--implementation\">Python <meta charset=\"utf-8\">Implementation<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a set of <strong>N<\/strong> items each having value <strong>V <\/strong>with weight <strong>W<\/strong> and the total capacity of a knapsack. The task is to find the maximal value of fractions of items that can fit into the knapsack.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><br><strong>Input:<\/strong> A[] = {{60, 20} , {100, 50}, {120, 30}}, Total_capacity&nbsp; = 50<br><strong>Output:<\/strong> 180.00<br><strong>Explanation:<\/strong> Take the first item and the third item. Total value = 60 + 120 = 180 with a total capacity of 20 + 30 = 50<\/p>\n\n\n\n<p><strong>Input: <\/strong>A[] = {{500, 30}}, Total_capacity = 10<br><strong>Output:<\/strong> 166.67<br><strong>Explanation:<\/strong> Since the total capacity of the knapsack is 10, consider one-third of the item.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"brute-force-approach\">Brute Force Approach<\/h2>\n\n\n\n<p>The most basic approach is to try all possible subsets and possible fractions of the given set and find the maximum value among all such fractions.<\/p>\n\n\n\n<p>The time complexity will be exponential, as you need to find all possible combinations of the given set.<\/p>\n\n\n\n<h2 id=\"efficient-approachgreedy\">Efficient Approach(Greedy)<\/h2>\n\n\n\n<p>The Fractional Knapsack problem can be solved efficiently using the greedy algorithm, where you need to sort the items according to their <strong>value\/weight <\/strong>ratio.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"484\"  height=\"714\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"value\/weight ratio\"  class=\"wp-image-2720 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 484px) 100vw, 484px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/value-weight-ratio.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/value-weight-ratio.png 484w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/value-weight-ratio-203x300.png 203w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/value-weight-ratio-380x561.png 380w\" ><\/figure>\n\n\n\n<p><strong>Algorithm&nbsp;<\/strong><\/p>\n\n\n\n<ul><li>Sort the given array of items according to <strong>weight \/ value(W \/V) <\/strong>ratio in descending order.<\/li><li>Start adding the item with the maximum <strong>W \/ V<\/strong> ratio.<\/li><li>Add the whole item, if the current weight is less than the capacity, else, add a portion of the item to the knapsack.<\/li><li>Stop, when all the items have been considered and the total weight becomes equal to the weight of the given knapsack.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"854\"  height=\"427\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"total capacity\"  class=\"wp-image-2721 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 854px) 100vw, 854px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/total-capacity.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/total-capacity.png 854w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/total-capacity-300x150.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/total-capacity-768x384.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/total-capacity-380x190.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/total-capacity-550x275.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/total-capacity-800x400.png 800w\" ><\/figure>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">struct item\n{\n    int value,weight;\n};\nbool cmp(item a,item b)\n{\n    double r1=(double)a.value\/a.weight;\n    double r2=(double)b.value\/b.weight;\n    return(r1>r2);\n}\ndouble fractionalknapsack(item A[],int Total_Capacity,int n)\n{\n    sort(A,A + n,cmp);\n    int cur_weight = 0;\n    double final_val = 0.0;\n    for(int i=0;i&lt;n;i++)\n    {\n        if(cur_weight + arr[i].weight &lt;= Total_Capacity)\n        {\n            Cur_weight += A[i].weight;\n            Final_val += A[i].value;\n        }\n        else\n        {\n            int remain = Total_capacity - cur_weight;\n            Final_val += A[i].value * ((double)remain \/ A[i].weight);\n        }\n    }\n    return final_val;\n}<\/pre>\n\n\n\n<h3 id=\"java--implementation\"><span id=\"java-implementation\">Java <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">fractionalknapsack(int[] val,int[] weights, int tot_capacity)                               {\n        Items[] iVal = new Items[weight.length];\n  \n        for (int i = 0; i &lt; wt.length; i++) {\n            iVal[i] = new Item(weight[i], value[i], i);\n        }\n  \n        Arrays.sort(iVal, new Comparator&lt;ItemValue>() {\n            @Override\n            public int compare(Items o1, Items o2)\n            {\n                return o2.cost.compareTo(o1.cost);\n            }\n        });\n  \n        double totalValue = 0d;\n  \n        for (Items i : iVal) {\n  \n            int curWt = (int)i.weight;\n            int curVal = (int)i.value;\n  \n            if (capacity - curWt >= 0) {\n                capacity = capacity - curWt;\n                totalValue += curVal;\n            }\n            else {\n               double fraction = ((double)capacity \/ (double)curWt);\n                totalValue += (curVal * fraction);\n\n               capacity\n                    = (int)(capacity - (curWt * fraction));\n                break;\n            }\n        }\n  \n        return totalValue;\n    }\n  \n    static class Items {\n        double cost;\n        double weight, value, ind;\n  \n        public ItemValue(int weight, int value, int ind)\n        {\n            this.wt = wt;\n            this.val = val;\n            this.ind = ind;\n            cost = new Double((double)value \/ (double)weight);\n        }\n    }<\/pre>\n\n\n\n<h3 id=\"python--implementation\"><span id=\"python-implementation\">Python <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def fractionalknapsack(values,weights,Total_capacity):\n    n = len(values)\n\n    def score(i) : return values[i]\/weights[i]\n\n    items = sorted(range(n)  , key=score , reverse = True)\n    sel, value,weight = [],0,0\n    for i in items:\n        if weight +weights[i] &lt;= capacity:\n            sel += [i]\n            weight += weights[i]\n            value += values [i]\n    return value<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N *log N) where N is the size of the array<strong>.<\/strong><br><strong>Space Complexity:<\/strong> O(1) because no extra space is needed.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/0-1-knapsack\/\" target=\"_blank\" rel=\"noreferrer noopener\">0-1 Knapsack<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>How do you solve fractional knapsack?<br><\/strong>Fractional knapsack can be solved using greedy algorithms.<\/p>\n\n\n\n<p><strong>What is the time complexity of fractional knapsack problems?<br><\/strong>The time complexity of the fractional knapsack problem is O(NlogN).<\/p>\n\n\n\n<p><strong>Can we solve fractional knapsack using dynamic programming?<br><\/strong>Yes, fractional knapsack can be solved using dynamic programming, but it will not be efficient as it will take memory.<\/p>\n\n\n\n<p><strong>Which approach is the best in knapsack problems?<\/strong><br>For 0\/1 knapsack, the dynamic programming approach is the best, while for fractional knapsack, the greedy approach is optimal.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a set of N items each having value V with weight W and the total&hellip;\n","protected":false},"author":4,"featured_media":2719,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[457,454],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2657"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2657"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2657\/revisions"}],"predecessor-version":[{"id":2724,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2657\/revisions\/2724"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2719"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2657"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2657"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2657"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}