Java 比较器 reversed() 方法有奇怪的结果

Question

我有一个关于分数背包问题的编程作业。作为问题的解决方案，我们需要按照 profit/weight 比率的降序填充项目。我使用自定义比较器对项目进行排序。

检查下面class项中的profitByWeightComparator：

class Item {
  private int itemNumber;
  private int profit;
  private int weight;

  public Item() {
    profit=weight=0;
  }
  public Item(int itemNumber, int profit, int weight) {
    this.itemNumber = itemNumber;
    this.profit = profit;
    this.weight = weight;
  }
  public String toString() {
    return "("+this.getItemNumber()+", "+this.getProfit()+", "+this.getWeight()+")";
  }
  public static Comparator<Item> profitByWeightComparator = new Comparator<Item>() {
    @Override
    public int compare(Item item1, Item item2) {
      double item1Ratio = (double)(item1.getProfit()/item1.getWeight());
      double item2Ratio = (double)(item2.getProfit()/item2.getWeight());
      return new Double(item1Ratio).compareTo(new Double(item2Ratio));
    }
  };
  public int getItemNumber() {
    return this.itemNumber;
  }
  public int getProfit() {
    return this.profit;
  }
  public int getWeight() {
    return this.weight;
  }
}

我使用比较器class的reversed()方法进行降序排序

检查下面KnapSackclass中的fillGreedyByProfitPerWeight()方法：

class KnapSack {
  Item [] items;
  int capacity;
  KnapSack() {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter number of items: ");
    int n = sc.nextInt();
    items = new Item[n];
    System.out.println("Enter the capacity of the KnapSack: ");
    this.capacity = sc.nextInt();

    int profit = 0;
    int weight = 0;

    for(int i = 0; i < n; i++) {
      System.out.println("Enter Item "+(i+1)+" (Format - Profit<Space>Weight):");
      profit = sc.nextInt();
      weight = sc.nextInt();
      items[i] = new Item((i+1), profit, weight);
    }
    fillGreedyByProfitPerWeight();
  }
  public void fillGreedyByProfitPerWeight() {
    Arrays.sort(items,Item.profitByWeightComparator.reversed());
    fillKnapSack("Greedy by Profit Per Weight");
  }
  public void fillKnapSack(String strategy) {
    double totalProfit = 0d;
    int currItemProfit = 0, currItemWeight = 0, i=0, tempCapacity = capacity;
    ArrayList<Integer> filledItems = new ArrayList<Integer>();
    System.out.println(Arrays.toString(items));
    for(i = 0; i < items.length; i++) {
      currItemProfit = items[i].getProfit();
      currItemWeight = items[i].getWeight();
      if(currItemWeight <= tempCapacity) {
        filledItems.add(items[i].getItemNumber());
        totalProfit += currItemProfit;
        tempCapacity -= currItemWeight;
      }
      else {
        break;
      }
    }
    double fraction = (double)tempCapacity/currItemWeight;
    totalProfit += (double)(currItemProfit*fraction);
    System.out.println("KnapSack filled using strategy: "+strategy+".\nMaximum Profit: "+totalProfit);
    System.out.print("Items added: ");
    for(int k:filledItems) {
      System.out.print(k+" ");
    }
    if(fraction != 0d)
      System.out.print("and "+tempCapacity+"/"+currItemWeight+" of "+items[i].getItemNumber());
    System.out.println("\n");
  }

  public static void main(String[] args) {
    KnapSack obj = new KnapSack();
  }
}

然而，在某些情况下它会导致奇怪的结果。例如当我尝试以下输入时：

No. of Items: 5
Capacity: 20
Item 1 (Format - Profit<space>Weight): 20 1
Item 2 (Format - Profit<space>Weight): 10 1
Item 3 (Format - Profit<space>Weight): 10 2
Item 4 (Format - Profit<space>Weight): 40 8
Item 5 (Format - Profit<space>Weight): 60 11

Maximum Profit的预期输出为125（Item 1，Item 2，Item 5，Item 3 and 5/8 of Item 4），但得到的输出如下：（请检查 link 因为我还不允许嵌入图像）

Output Screenshot

请注意，排序顺序混乱，因为第 5 项不应该倒序排列在最后，它必须排在第三位。罪魁祸首可能是什么？

Answer 1

您的比较器错误地执行除法：它不是先将 int 转换为 double 然后进行除法，而是先进行除法，然后再将结果转换为 double。那时分数已经没有了，所以结果排序不正确。

更改比较器如下：

public static Comparator<Item> profitByWeightComparator = new Comparator<Item>() {
    @Override
    public int compare(Item item1, Item item2) {
        double item1Ratio = ((double)item1.getProfit())/item1.getWeight();
        double item2Ratio = ((double)(item2.getProfit())/item2.getWeight();
        return Double.compare(item1Ratio, item2Ratio);
    }
};

现在除法在double秒内完成，比较不截断小数部分

如果权重严格为正，并且 profit * weight 不会溢出 int，您可以完全跳过除法，比较比率如下：

public static Comparator<Item> profitByWeightComparator = new Comparator<Item>() {
    @Override
    public int compare(Item item1, Item item2) {
        return Integer.compare(
            item1.getProfit() * item2.getWeight()
        ,   item2.getProfit() * item1.getWeight()
        );
    }
};

Java 比较器 reversed() 方法有奇怪的结果

Java Comparator reversed() method has weird results

java

sorting

knapsack-problem

comparator