C++ Greedy Approach Fractional Knapsack














































C++ Greedy Approach Fractional Knapsack



Fractional Knapsack Problem

Given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack
Input: 
Items as (value, weight) pairs 
arr[] = {{60, 10}, {100, 20}, {120, 30}} 
Knapsack Capacity, W = 50; 
Output:
Maximum possible value = 240
By taking full items of 10 kg, 20 kg and
2/3rd of last item of 30 kg
In Fractional Knapsack, we can break items for maximizing the total value of knapsack. This problem in which we can break an item is also called the fractional knapsack problem. 

brute-force solution would be to try all possible subset with all different fraction but that will be too much time taking. 

An efficient solution is to use Greedy approach. The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can%u2019t add the next item as a whole and at the end add the next item as much as we can. Which will always be the optimal solution to this problem.

A simple code with our own comparison function can be written as follows, please see sort function more closely, the third argument to sort function is our comparison function which sorts the item according to value/weight ratio in non-decreasing order. 
After sorting we need to loop over these items and add them in our knapsack satisfying above-mentioned criteria.

Below is the implementation of the above idea:


#include <bits/stdc++.h>

using namespace std;


struct Item
{
    int value, weight;

    
    Item(int value, int weight)
        : value(value)
        , weight(weight)
    {
    }
};

bool cmp(struct Item a, struct Item b)
{
    double r1 = (double)a.value / (double)a.weight;
    double r2 = (double)b.value / (double)b.weight;
    return r1 > r2;
}

double fractionalKnapsack(int W, struct Item arr[], int n)
{
    
    sort(arr, arr + n, cmp);

    int curWeight = 0;
    double finalvalue = 0.0;

    for (int i = 0; i < n; i++)
    {
        
        if (curWeight + arr[i].weight <= W)
        {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        }

    
        else
        {
            int remain = W - curWeight;
            finalvalue
                += arr[i].value
                * ((double)remain / (double)arr[i].weight);
            break;
        }
    }

    
    return finalvalue;
}

int main()
{
    int W = 70;
    Item arr[] = { { 50, 10 }, { 120, 20 }, { 210, 30 } };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Maximum value we can obtain = "
        << fractionalKnapsack(W, arr, n);
    return 0;
}

-------------------------------------------------------------------
Output:
Maximum value we can obtain = 380





More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 146 0
C++ Sieve Of Erastosthenes 105 0
C++ Gold Mine Problem 247 0
C++ Merge K Sorted Arrays 97 0
C++ K Centers Problem 217 0
C++ Find Nth Catalan Number 289 0
C++ Inplace Rotate square matrix by 90 degrees 259 0
C++ Find Non Repeating Elements in Array 63 0
C++ Merge Two Binary Trees 90 0
C++ Sum of Numbers From Root To Leaf Paths 70 0
C++ Meta Strings 76 0
C++ Flood Fill Algorithm 375 0
C++ smallest substring with maximum distinct characters 113 0
C++ Smallest window with all characters in string 72 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 71 0
C++ Minimum characters added at front of string in palindrome conversion 55 0
C++ Number of Bracket Reversals needed to make expression Balanced 59 0
C++ String to Palindrome with Append Function 58 0
C++ WildCard pattern matching 61 0
C++ Anagram substring Search 55 0
C++ Manachars Algorithm 60 0
C++ Search String in Grid 66 0
C++ String Matching(Z Algorithm) 55 0
C++ String Matching(Naive Algorithm) 82 0
C++ String Matching(KMP Algorithm) 118 0
C++ Remove Duplicates From String 71 0
C++ Basics of String Manipulation 71 1
C++ Disjoint Data Structure Cycle Detection 73 0
C++ Problem On Disjoint Data Structures 65 0
C++ Disjoint Data Structures Part3 65 0
Disjoint Data Structures Part2 79 0
Disjoint Data Structures 81 1
C++ Segment Trees 292 2
C++ Trie Cost of Data 259 1
C++ Trie Datastructure 251 1
C++ Greedy Approach Minimum number of coins 457 0
C++ Greedy Approach Maximum height Pyramid 293 1
C++ Greedy Approach String lexicographically largest subsequence 202 0
C++ Greedy Approach Lexicographically largest subsequence 339 0
C++ Greedy Approach Prims MST 360 1
C++ Greedy Approach Krushkals MST 421 1
C++ Greedy Approach N-array maximum sum 314 1
C++ Greedy Approach Policemen Catch Thieves 539 1
C++ Greedy Approach Maximum product Subset 519 1
C++ Greedy Approach Minimum Product Subset 319 1
C++ Greedy Approach Fractional Knapsack 656 1
C++ Greedy Approach-Activity Selection Problem 653 1
C++ Greedy Approach-Egyptian Fractions 592 0
C++ Greedy Approach-Huffman Codes 815 1
C++ Introduction to Greedy Approach 923 2

Comments