Java Comparator reversed() method has weird results

Question

I have a programming assignment regarding the Fractional Knapsack Problem. As is the solution for the problem, we need the items to be filled in the descending order of their profit/weight ratio. I used a custom Comparator for sorting the items.

Check the profitByWeightComparator in the Item class below:

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

I used the reversed() method of the Comparator class to sort in descending order.

Check the fillGreedyByProfitPerWeight() method in the KnapSack class below:

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

However, it leads to weird results in some cases. For e.g. When I try the following inputs:

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

Expected output for Maximum Profit is 125 (Item 1, Item 2, Item 5, Item 3 and 5/8th of Item 4), but the obtained output is as follows: (Please check the link as I am not allowed to embed images yet)

Output Screenshot

Note that the sort order is messed up, as Item 5 should not be last in the reversed sorted order, it must be 3rd. What might be the culprit here?

Answer 1

Your comparator performs division incorrectly: rather than converting int to double and then dividing, it divides first, and then converts the result to double. The fraction is gone by then, so the results do not sort correctly.

Change the comparator as follows:

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

Now the division is done in doubles, and comparison is done without truncating the fractional part.

If weights are strictly positive, and profit * weight does not overflow an int, you can skip division altogether, comparing ratios like this:

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