最差啓發式優先級隊列的比較

我正在嘗試使用最適合的啓發式方法編寫一個bin包裝程序，以便它將權重添加到bin中，直到它們無法再存儲爲止，因爲它們被文件讀取，將倉位序列放入優先級隊列中，以便將倉位最小的倉位置於頂部。但是我在編寫Bin類的比較器時遇到了麻煩。下面是完整的代碼：最差啓發式優先級隊列的比較

public class BinPacking{ 

    public static class Bin implements Comparable<Bin> { 

     int ID ; 
     int remSpace; 
     ArrayList<Integer> weights = new ArrayList<Integer>(); 

     public Bin(int ID){ 
      this.ID = ID; 
      remSpace = 100; 
     } 

     public void add(int size){ 
      remSpace -= size; 
      weights.add(size); 
     } 

     @Override 
     public int compareTo(Bin o) { 
      return remSpace; 
     } 

} 



    public static void main(String[] args) throws FileNotFoundException{ 


     PriorityQueue<Bin> pq =new PriorityQueue<Bin>(); 

     File myFile = new File("input.txt"); 

     int binId = 1; 
     Bin d = new Bin(binId); 
     pq.add(d); 
     int size; 


     Scanner input = new Scanner(myFile); 

     while (input.hasNext()) 
     { 

      size = input.nextInt(); 

      d = (Bin)pq.peek(); 

      if (d.remSpace >= size) 
      { 
       pq.remove(d); 
       d.add(size); 
       pq.add(d); 

      } 
      else 
      { 
       binId++; 
       d = new Bin(binId); 
       d.add(size); 
       pq.add(d); 



      } 
     } 
     System.out.println("Number of bins used: " + binId); 

     int mylst[][] = new int[binId][1000]; 
     int k =1; 
     for(int i=0;i<binId;i++){ 
      System.out.println("Bin" + k + ": "); 
      k++; 
      for(int j=0;j<pq.peek().weights.size();j++){ 

       mylst[i][j] = pq.peek().weights.get(j); 
       System.out.print(" "+mylst[i][j]); 
      } 
      System.out.println(); 
      pq.poll(); 
     } 



    } 
}

來源

2013-05-01 Umut

Comparable#compareTo(T)意味着返回兩個對象之間的差異，允許算法來決定一個項目是否i等於，比另一個更小或更大。返回剩餘的空間不會給你比你想要的，因爲這不是比較這兩個對象。請嘗試：

public int compareTo(Bin o) { 
    if(o == null)return 1; 
    if(remSpace > o.remSpace)return 1; 
    else if(remSpace < o.remSpace)return -1; 
    return 0; 
}

請注意，這是如何返回兩個倉的空間差異，以便可以計算出差異。

來源

2013-05-01 00:16:11 Sinkingpoint

雖然這是一種邊緣情況，但不建議使用直接減法，因爲溢出會給出不正確的結果。典型的方法是實際執行比較，並根據情況返回-1,0或1。同樣，防止空值是值得的。 – dlev 2013-05-01 00:28:23

固定。謝謝指出。我以爲我可以偷工減料...... – Sinkingpoint 2013-05-01 00:30:22

說實話，在這種情況下，這可能是一個非問題，因爲我無法想象其他任何合理的代碼會給'remSpace'賦予一個負值，所以不應該溢出發生。只是要記住的道路:) – dlev 2013-05-01 00:35:05

最差啓發式優先級隊列的比較

回答

相關問題