arraylist 使用 collections.sort() 排序时出错

Question

我正在写关于分数背包的代码。但是，排序算法效果不佳。因此我的代码无法正常工作。

这是我的代码：

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

}

我尝试使用简单的数组而不是数组列表，它工作正常，但我的老师想编写代码来实现 collections.sort() 和比较器类。 这是输入 8个 40 20 10 30 15 18 5 25 12 14 6 24 8 15 7 10 3

预期产出 103.91 实际产量 100.0

但是，我这里的代码只接近 100，因此它不完全正确。

Answer 1

我尝试使用简单的数组而不是 arraylist，它工作正常

我觉得很难相信。您创建的

Comparator

是有缺陷的，无论是与数组一起使用还是与

List

一起使用。

您正在根据

Item.ppw

进行排序，这是一个

float

。这本身并没有错，但请考虑您的具体实施：

        return (int) (o2.ppw) - (int) (o1.ppw);  

如果

o1.ppw

和

o2.ppw

不同，但

(int) o1.ppw

和

(int) o2.ppw

相同，则返回错误结果（

0

）

我倾向于猜测您试图为基于

int

的比较调整一个更微妙但相对常见的实现。使用两个

int

的差作为比较器的返回值比您的代码更正确，但如果减法溢出，它仍然会产生错误的答案。

别想这么聪明。这种一般形式的

Comparator

非常适合通过原始类型的任何单个字段比较对象：

class CompareByPPW implements Comparator<Item> {
    public int compare(Item o1, Item o2) {
        if (o1.ppw < o2.ppw) {
            return -1;
        } else if (o2.ppw < o1.ppw) {
            return 1;
        } else {
            return 0;
        }
    }
}