java - 分数背包问题

Question

这是我用 Java 实现的代码。 getmax() 函数返回最大元素的索引。问题是，我没有得到正确的测试用例之一。我不知道是哪一个，但在线法官给我以下警告:

Failed case #7/13: Wrong answer got: 66152.57 expected: 66152.572 (Time used: 0.19/1.50, memory used: 24469504/671088640.)

public class FractionalKnapsack {
private static double getOptimalValue(int capacity, int[] values, int[] weights) {
    float value = 0;
    //write your code here
    float[] ratio=new float[values.length];
    for(int i=0;i<values.length;i++)
    {
        ratio[i]=(float)values[i]/(float)weights[i];
    }
    int max=0;

    while(capacity>-1)
    {
        max=getMax(ratio);
        if(capacity==0)
        {
            return value;
        }
        if(capacity>0)
        {
            if(weights[max]>=capacity)
            {
                value=value+((float)ratio[max]*(float)(capacity));
                capacity=0;
            }
            else if(capacity>weights[max])
            {
                value=value+(weights[max]*ratio[max]);
                capacity=capacity-weights[max];
            }
            ratio[max]=0;
        }
    }
    return value;
}
private static int getMax(float[] arr)
{
    float max=0;
    int save=0;
    for(int i=0;i<arr.length;i++)
    {
        if(arr[i]>max)
        {
            max=arr[i];
            save=i;
        }
    }
    return save;
}
public static void main(String args[]) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int capacity = scanner.nextInt();
    int[] values = new int[n];
    int[] weights = new int[n];
    for (int i = 0; i < n; i++) {
        values[i] = scanner.nextInt();
        weights[i] = scanner.nextInt();
    }
    DecimalFormat df = new DecimalFormat();
    df.applyPattern(".0000");
    System.out.println(df.format(getOptimalValue(capacity, values, weights)));
}

}

Answer 1

您使用的 float 类型无法区分 66152.57(您的输出)和 66152.572(所需输出)。你可以查一下here例如，在线。看，尾数只有 23 位的存储空间，这意味着相对误差可以达到 2^-24 的数量级。对于 66152.572 星等，它意味着 0.003943 的绝对误差。如果您对原因更感兴趣，请查阅一些浮点指南(例如 this one )。

解决方案是使用double 进行浮点计算。 请注意，除非您确实知道 float 精度对您的应用程序来说已经足够，否则 double 几乎总是可以用来避免此类不幸影响的正确类型。