使用Collections.sort()对ArrayList排序出错致分数背包计算异常

我正在编写分数背包的Java代码，但排序算法运行异常，导致代码计算结果不正确。尝试使用普通数组替代ArrayList时计算结果正常，但老师要求代码必须使用Collections.sort()和Comparator类实现排序。

输入数据 #

8
40
20 10
30 15
18 5
25 12
14 6
24 8
15 7
10 3

预期与实际输出 #

• 预期输出：103.91
• 实际输出：100.0

我的代码 #

import java.util.*;
class Item {
    int profit, weight;
    float ppw;
    //ppw is profit per weight
    public Item(int profit, int weight) {
        this.profit = profit;
        this.weight = weight;
        this.ppw= (float)profit / (float)weight;
    }
}

class SortbyPPW implements Comparator<Item> {
    public int compare(Item o1, Item o2) {
        return (int) (o2.ppw) - (int) (o1.ppw);  
    }
}

public class FractionalKnapSack {
    public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter the number of elements: ");
    int n = sc.nextInt();
    System.out.print("Enter maximum capacity: ");
    int capacity = sc.nextInt();
    System.out.println("\nEnter the items with their profit and weight separated by a space");

    ArrayList<Item> items = new ArrayList<Item>();
    for (int i = 0; i < n; i++) {
        int profit = sc.nextInt();
        int weight = sc.nextInt();
        items.add(new Item(profit, weight));
    }

    System.out.println("\n");
    for (Item item : items)
        System.out.print(item.ppw+" ");
    System.out.println("\n");


    System.out.println(Arrays.toString(items.toArray()));
    double[] maxValue = getMaxValue(items, capacity);
    System.out.println("\nMaximum profit we can obtain = " + maxValue[0]);
    System.out.println("Capacity Used = " + (capacity-maxValue[1]));
    System.out.println("\n");
    System.out.println(Arrays.toString(items.toArray()));

    System.out.println("\n");
    for (Item item : items)
        System.out.print(item.ppw+" ");
    System.out.println("\n");
}

public static double[] getMaxValue(ArrayList<Item> items, int capacity) {
    double maxValue = 0;
    Collections.sort(items, new SortbyPPW());

    for (Item item : items) {
        int currWeight = item.weight;
        int currValue = item.profit;

        if (capacity - currWeight >= 0) {
            capacity -= currWeight;
            maxValue += currValue;
        } else {
            double fraction = ((double) capacity / (double) currWeight);
            maxValue += (currValue * fraction);
            capacity = (int) (capacity - (currWeight * fraction));
            break;
        }
    }
    double[] arr1={maxValue, (double)capacity} ;
    return arr1;
}
}

问题原因 #

排序逻辑出错了！SortbyPPW类的compare方法中，将float类型的ppw强制转换为int后再做减法，会丢失小数部分的精度。比如：

• 18/5=3.6，转int后是3
• 10/3≈3.333，转int后也是3
• 24/8=3.0，转int后还是3

这些物品的ppw实际大小有差异，但转int后被判定为相等，导致排序时无法按照真实的单位重量利润降序排列，最终选出来的物品组合不是最优的，利润计算结果偏低。

解决方案 #

修改SortbyPPW的compare方法，直接使用Float.compare()来比较两个float值，这样能保留完整精度，返回正确的排序结果：

class SortbyPPW implements Comparator<Item> {
    public int compare(Item o1, Item o2) {
        return Float.compare(o2.ppw, o1.ppw);  
    }
}

验证结果 #

修改后，物品会按照ppw从高到低正确排序：
3.6（18/5）→3.333（10/3）→3.0（24/8）→2.333（14/6）→2.142（15/7）→2.083（25/12）→2.0（20/10）→2.0（30/15）

按照这个顺序选取物品，计算过程如下：

1. 取18/5的物品：重量5，利润18，剩余容量40-5=35，总利润18
2. 取10/3的物品：重量3，利润10，剩余容量35-3=32，总利润28
3. 取24/8的物品：重量8，利润24，剩余容量32-8=24，总利润52
4. 取14/6的物品：重量6，利润14，剩余容量24-6=18，总利润66
5. 取15/7的物品：重量7，利润15，剩余容量18-7=11，总利润81
6. 取25/12的物品：重量12，剩余容量11<12，取11/12的部分，利润25*(11/12)≈22.9167，总利润81+22.9167≈103.9167，四舍五入后就是预期的103.91

内容的提问来源于stack exchange，提问作者Saransh Shukla