java - 最坏拟合启发式优先级队列的比较器

Question

我正在尝试使用最差拟合启发式编写一个装箱程序，以便将权重添加到箱中，直到它们在被文件读取时无法再存储为止，并将箱序列放入优先级队列中这样它将剩余空间最少的垃圾箱放在顶部。但我在编写 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();
       }



    }
}

Answer 1

Comparable#compareTo(T)旨在返回两个对象之间的差异，允许算法决定一个项目是否等于、小于或大于另一个项目。返回 1 的剩余空间不会给出比您想要的顺序，因为这不会比较两个对象。尝试:

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

注意它如何返回两个 Bin 的空间差异，以便可以测量差异。