java - 小背包问题

这是我用Java实现的代码GETMax（）函数返回最大元素的索引。问题是，我没有使我的测试用例正确。我不知道是哪一个，但网上法官给了我以下警告：
失败案例7/13：答错
得到：66152.57预期：66152.572
（使用时间：0.19/1.50，使用内存：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)));
}

}

最佳答案

您使用的float类型无法区分66152.57（您的输出）和66152.572（所需的输出）。例如，您可以在线查看它。看，尾数只有23位存储，这意味着相对误差可能在2-24之间对于震级66152.572，表示绝对误差为0.003943。如果您对“为什么”更感兴趣，请查阅一些浮点指南（如here）。
解决方法是使用double进行浮点计算。
请注意，除非您真正知道float精度对于您的应用程序来说已经足够了，double几乎总是避免这种不幸影响的正确类型。