最差启发式优先级队列的比较

我正在尝试使用最适合的启发式方法编写一个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

最差启发式优先级队列的比较

回答

相关问题