Heap Book Box Packing

Question

책의 순서로 읽은 프로그램을 힙에 저장하고 책을 무게에 따라 상자에 효율적으로 포장하는 욕심 많은 알고리즘을 구현하는 프로그램을 작성하려고합니다.

올바르게 힙을 구현하는 데 문제가 있습니다.

힙에 추가하는 방법은 addLastChild()입니다. 그것은 힙의 다음 위치를 찾아 새로운 책을 삽입하고 그 무게에 따라 재구성해야합니다.

여기에 추가 코드 :

public void addLastChild(Book newBook) 
{ 
    Book[] pathList = new Book[30]; 
    int tracker = 0; 

    int cnt = BookCnt+1; 
    String path = ""; 
    while(cnt >= 1) 
    { 
     path = (cnt %2) + path; 
     cnt = cnt/2; 
    } 

    Book c = root; 

    if(root!=null) 
    { 
     pathList[tracker]=root; 
     tracker++; 
    } 

    for(int i = 1; i < path.length()-1; i++){ 
     if(path.charAt(i)== '0') { 

      c = c.left; 
      pathList[tracker]=c; 
      tracker++; 
     } else { 

      c = c.right; 
      pathList[tracker]=c; 
      tracker++; 
     } 
    } 
    if(path.length() == 1) 
    { 
     root = newBook; 
    } 
    else if(path.charAt(path.length()-1)== '0') { 
     c.left = newBook; 
     pathList[tracker]=c.left; 
     tracker++; 

    } 
    else 
    { 
     c.right = newBook; 
     pathList[tracker]=c.right; 
     tracker++; 
    } 
    BookCnt++; 

    boolean doTrickle = false; 
    if(tracker>=2) 
    { 
     doTrickle = true; 
    } 

    while(doTrickle == true) 
    { 
     Book temp = new Book(pathList[tracker-2].refNumber, pathList[tracker-2].weight, pathList[tracker-2].title, null,null); 
     //int refNumber, int weight, String title, Book left, Book right 
     print(root," "); 

     if(pathList[tracker-1].weight > pathList[tracker-2].weight) 
     { 

      pathList[tracker-2].refNumber=pathList[tracker-1].refNumber; 

      pathList[tracker-2].title=pathList[tracker-1].title; 
      pathList[tracker-2].weight=pathList[tracker-1].weight; 

      if(pathList[tracker-2].left == pathList[tracker-1]) 
      { 
       pathList[tracker-2].left = temp; 
      } 
      if(pathList[tracker-2].right == pathList[tracker-1]) 
      { 
       pathList[tracker-2].right = temp; 
      } 

      tracker--; 

      System.out.println("we trickled"); 
      print(root," "); 
     } 
     else 
     { 
      doTrickle =false; 
     } 
    } 

} 

나는 힙에서 제거하기 위해 사용하고있는이 방법은 removeLastChild()이며 removeLastChild() 메소드는 힙의 마지막 책을 반환) (제거, remove()는 가장 큰 가중치를 가진 책을 반환하고 루트를 마지막 책으로 바꾼 다음 그에 따라 힙을 재구성해야합니다. 도움말에 대한

Book removeLastChild() { 
    int cnt = BookCnt; 
    String path = ""; 
    while(cnt >= 1) 
    { 
     path = (cnt %2) + path; 
     cnt = cnt/2; 
    } 

    Book returnBook = null; 
    Book c = root; 
    for(int i = 1; i < path.length()-1; i++){ 
     if(path.charAt(i)== '0') { 
      c = c.left; 
     } else { 
      c = c.right; 
     } 
    } 
    if(path.length() == 1) 
    { 
     returnBook = root; 
     root = null; 
    } 
    else if(path.charAt(path.length()-1)== '0') { 
     returnBook = c.left; 
     c.left = null; 
    } 
    else 
    { 
     returnBook = c.right; 
     c.right = null; 
    } 
    BookCnt--; 
    return returnBook; 
} 

Book remove() 
{ 

    Book largest =root; 
    root = removeLastChild(); 

    if(largest.left!= null) 
    { 
     root.left = largest.left; 
    } 
    if(largest.right!= null) 
    { 
     root.right = largest.right; 
    } 



    Book cur = root; 

    if(root!= null) 
    { 
     while(cur.left !=null && cur.right!= null) 
     { 
      if(cur.weight<cur.left.weight || cur.weight<cur.right.weight) 
      { 
       Book temp = new Book(cur.refNumber, cur.weight, cur.title, null, null); 
       //int refNumber, int weight, String title, Book left, Book right 

       if(cur.left.weight>cur.right.weight) 
       { 
         cur.refNumber = cur.left.refNumber; 

        cur.title = cur.left.title; 
        cur.weight = cur.left.weight; 


        cur.left.refNumber = temp.refNumber; 
        cur.left.weight = temp.weight; 
        cur.left.title = temp.title; 
        cur = cur.left; 

       } 
       else 
       { 

        cur.refNumber = cur.right.refNumber; 

        cur.title = cur.right.title; 
        cur.weight = cur.right.weight; 

        cur.right.refNumber = temp.refNumber; 
        cur.right.weight = temp.weight; 
        cur.right.title = temp.title; 
        cur = cur.right; 

       } 

      } 
      else 
      { 
       return largest; 
      } 
     } 
    } 
    return largest; 

} 

감사 :

다음은 나에게 문제를주고 제거 코드입니다!

나는 분명히 의사 소통하지 못한 것을 분명히 밝힙니다.

Answer 1

힙 구현에 대한 대안을 제시하고 배낭 문제에 대한 욕심 많은 알고리즘의 목표를 부여한다면 간단히 PriorityQueue을 사용하지 않는 이유는 무엇입니까?

"우선 순위 힙을 기반으로 한 무제한 우선 순위 큐 : 우선 순위 큐의 요소는 자연 순서에 따라 정렬되거나 큐 생성 시간 (...)에 제공된 비교 자로 정렬"

책 클래스는이 같은 Comparable 인터페이스를 구현하는 경우

는 (예제의 책은 매우 단순화) :

는

class Book implements Comparable<Book>{ 
     public String title; 
     public int weight; 

     public Book(int weight, String title) { 
      this.weight = weight; 
      this.title = title; 
     } 

     @Override 
     public int compareTo(Book anotherBook) { 
      return weight - anotherBook.weight; 
     } 
    } 

책의 자연 순서는 함께 책에 최소한의 무게로 책을 가야한다 대부분의 무게. 우선 순위 큐에 예약 클래스를 사용

:

public static void main(String[] args) { 
     Book book1 = new Book(10,"a"); 
     Book book2 = new Book(11,"b"); 
     Book book3 = new Book(20,"c"); 
     Book book4 = new Book(20,"d"); 
     Book book5 = new Book(11,"e"); 

     PriorityQueue<Book> bookQueue = new PriorityQueue<Book>(); 
     bookQueue.add(book1); 
     bookQueue.add(book2); 
     bookQueue.add(book3); 
     bookQueue.add(book4); 
     bookQueue.add(book5); 

     while(!bookQueue.isEmpty()){ 
      Book book = bookQueue.poll(); 
      System.out.println(book.title + " - " + book.weight); 
     } 
    } 

당신은 당신이 당신의 상자에 넣어하는 데 필요한 방법을 책을 반복 할 수 있어야한다.