Myntra , fractional knapsnack problem

general
1

the below code is for fractional knapsnack problem , I have tried this using pair , but it seems some of the test cases are getting failed. Can anyone spot where the problems might be.

class Solution
{
public:
//Function to get the maximum total value in the knapsack.
double fractionalKnapsack(int W, Item arr[], int n)
{
// Your code here
pair<double,int> p[n];

    for(int i=0;i<n;i++){
        p[i].first = arr[i].value/arr[i].weight;
        p[i].second = i;
    }
    sort(p,p+n);
    
    double val =0;
    for(int i=n-1;i>=0;i--){
        
        
        if(arr[p[i].second].weight <= W){
            val += arr[p[i].second].value;
            W = W - arr[p[i].second].weight;
        }
        else{
            int index = p[i].second;
            val +=  W*((double)arr[index].value/arr[index].weight);
            break;
        }
    }
    return val;
}

};

2

Do you have a link to the problem?

1 Like
3

Yes here it is

4

What are the data types of arr[i].value and arr[i].weight?

If they are integers, typecast any one of them to float or double before performing division operation.

If they are already one of float, double there must be something else causing the issue.

2 Likes
5

This should be it, the other thing i saw is that his returning type is double, and the max capacity for the Knapsack will always be integer.

1 Like
6

You are mistaken. The Return type should be double. It signifies the maximum profit that can be obtained. The capacity of the bag is not a value returned, instead it is the value passed as an argument to the function.

1 Like
7

Yeah, you’re right, i thought it was something like just fill the bag, my bad.

8

hey suman thanx , it worked , i typcasted the “value” in double, when storing it in pair array.And now its working perfectly fine. Thank you soo much. I was soo much frustrated because of that.