최악의 적합성을 가진 휴리스틱 스 우선 순위 큐의 비교 자

Question

최악의 적합성을 가진 휴리스틱을 사용하여 bin-packing 프로그램을 작성하려고합니다. 파일에 의해 읽혀질 때까지 더 이상 저장할 수 없을 때까지는 가중치를 추가합니다. 빈의 순서를 우선 순위 대기열에 넣고 나머지 빈 공간이 가장 적은 빈을 맨 위에 놓습니다. 하지만 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)는 알고리즘이 하나 개의 항목 내가 다른 것보다보다 작거나 큰, 동일 여부를 결정할 수 있도록, 두 개체 사이의 차이를 반환하기위한 것입니다. 이 중 하나의 남은 공간을 반환하면 과 비교하면 두 객체를 비교할 때 원하는 것보다 순서가 부여되지 않습니다. 시도해보십시오 :

차이점을 측정 할 수 있도록 두 빈의 공백 차이를 어떻게 반환하는지주의하십시오.