Javaコンパレータのreversed（）メソッドに奇妙な結果があります

Question

フラクショナルナップザック問題に関するプログラミング課題があります。問題の解決策として、利益/重量比の降順で記入する必要があります。私はアイテムをソートするためにカスタムコンパレータを使いました。私は降順でソートするコンパレータクラスのreversed()メソッドを使用

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

：

は、以下の項目クラスのprofitByWeightComparatorを確認してください。

の下ナップザッククラスの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 

期待出力125（項目1、項目2、項目5、項目4の項3,5/8）が、以下のようにして得られた出力である：私は、次の入力をしようとしますソート順を台無しにされていることを （私はまだ画像を埋め込むことは許されないのですとしてリンクをご確認ください）

Output Screenshot

注、項目5は逆のソート順に最後のすべきではないとして、それがなければなりません3rd。ここでは何が原因でしょうか？

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