CODEWITHSUNDEEP
c++
coder_newbie
coder_newbie

Reputation: 39

Code is showing showing wrong output in 'fractional knapsack' problem even when answer is properly typecasted

I am solving question called fractional knapsack on geeks for geeks but I don't know why it is giving wrong output for a particular test case. I am not able to find any error in it.

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

struct Item{
    int value;
    int weight;
};


 // } Driver Code Ends
//class implemented
/*
struct Item{
    int value;
    int weight;
};
*/

static bool compare(Item i1,Item i2)
{
    double v1=i1.value/i1.weight;
    double v2=i2.value/i2.weight;
    
    return v1>v2;
}
class Solution
{
    public:
    //Function to get the maximum total value in the knapsack.
    double fractionalKnapsack(int W, Item arr[], int n)
    {
        // Your code here
        sort(arr,arr+n,compare);
        double ans=0.0;
        long long int i=0;
        while(i<n)
        {
            
            if(arr[i].weight<=W)
            {
                ans+=arr[i].value;
                W-=arr[i].weight;
            }
            else
            {
                double partialvalue=(double)((double)arr[i].value/(double)arr[i].weight)*(double)W;
                ans+=partialvalue;
                break;
            }
            i++;
        
        }
        return ans;
        
    }
        
};



// { Driver Code Starts.
int main()
{
    int t;
    //taking testcases
    cin>>t;
    cout<<setprecision(2)<<fixed;
    while(t--){
        //size of array and weight
        int n, W;
        cin>>n>>W;
        
        Item arr[n];
        //value and weight of each item
        for(int i=0;i<n;i++){
            cin>>arr[i].value>>arr[i].weight;
        }
        
        //function call
        Solution ob;
        cout<<ob.fractionalKnapsack(W, arr, n)<<endl;
    }
    return 0;
}  // } Driver Code Ends

RESULT: Wrong Answer. !!!Wrong Answer

Possibly your code doesn't work correctly for multiple test-cases (TCs).

The first test case where your code failed:

Input: 84 87 78 16 94 36 87 43 50 22 63 28 91 10 64 27 41 27 73 37 12 19 68 30 83 31 63 24 68 36 30 3 23 9 70 18 94 7 12 43 30 24 22 20 85 38 99 25 16 21 14 27 92 31 57 24 63 21 97 32 6 26 85 28 37 6 47 30 14 8 25 46 83 46 15 18 35 15 44 1 88 9 77 29 89 35 4 2 55 50 33 11 77 19 40 13 27 37 95 40 96 21 35 29 68 2 98 3 18 43 53 7 2 31 87 42 66 40 45 20 41 30 32 18 98 22 82 26 10 28 68 7 98 4 87 16 7 34 20 25 29 22 33 30 4 20 71 19 9 16 41 50 97 24 19 46 47 2 22 6 80 39 65 29 42 1 94 1 35 15

Its Correct output is: 1078.00

And Your Code's output is: 1075.57

Upvotes: 0

Views: 146

Answers (1)

idz
idz

Reputation: 12988

You forgot casts in your comparison function:

static bool compare(Item i1,Item i2)
{
    double v1=i1.value/i1.weight;
    double v2=i2.value/i2.weight;
    
    return v1>v2;
}

should be

static bool compare(Item i1,Item i2)
{
    double v1=(double)i1.value/(double)i1.weight;
    double v2=(double)i2.value/(double)i2.weight;
    
    return v1>v2;
}

There may be other issues, but this is the one that jumps out!

Upvotes: 3

Related Questions