即使正确地键入了答案，代码也会在“分数背包”问题中显示错误输出。

Question

我正在为极客解决一个叫做分数背包的问题，但是我不知道为什么它给了一个特定的测试用例错误的输出。我在里面找不到任何错误。

// { 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

结果：错误答案。！答错了

可能您的代码不能正确地用于多个测试用例(TCs)。

代码失败的第一个测试用例：

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

它的正确输出是: 1078.00

您的代码输出是: 1075.57

Answer 1

您在比较函数中忘记了转换：

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

应该是

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;
}

也许还有其他的问题，但这就是跳出的问题！