2

クラス タイプ BBNode のプライオリティ キューを実装しようとしていますが、期待どおりに新しいノードをふるいにかけないようです。最小のものをキューの先頭に置くのではなく (現在の動作)、最大のものをそこに置きたいのですが、これを機能させる方法がわかりません。これが私の BBNode クラスです。

public class BBNode implements Comparable<BBNode>{
    public int level; //level on the tree
    public int value; //value up to that node
    public int weight; //weight up to that node
    public double bound; //bound of that node

    //...constructors
    public int compareTo(BBNode node){
        if(this.bound > node.bound) return -1;
        if(this.bound < node.bound) return 1;
        return 0;
    }
}

ここで PQ を使用します。

PriorityQueue<BBNode> pq = new PriorityQueue<BBNode>();
//..other variables
while(pq.peek() != null){
  v = pq.poll();
  //System.out.println(v.weight + " " + v.value + " " + v.bound);
  if(v.bound >= bestVal && v.level < sortedItems.length-1){
     //left branch: take the next item
     u.level = v.level+1;
     u.weight = v.weight + sortedItems[u.level].weight;
     u.value = v.value + sortedItems[u.level].value;
     u.bound = bound(u);
     //System.out.println(u.bound);
     if(u.bound > bestVal){
        pq.add(u);
        System.out.println("adding " + u.bound);
        System.out.println("top of pq is " + pq.peek().bound);
     }
     if(u.weight <= maxWt && u.value > bestVal){
        bestVal = u.value;
        bestWt = u.weight;
        //System.out.println(bestVal + " " + bestWt);
        takeList[arrIdx++] = sortedItems[u.level].item+1;
     }
     //right branch: don't take the next item
     u.weight = v.weight;
     u.value = v.value;
     u.bound = bound(u);
     if(u.bound > bestVal){
        pq.add(u);
        System.out.println("adding " + u.bound);
        System.out.println("top of pq is " + pq.peek().bound);
     }
  }
}

最後のフォーマットがひどいので申し訳ありません。最後の括弧は while ループに対応します。

また、compare メソッドで -1 と 1 を切り替えてみました。Comparator も実装しようとしましたが、結果は同じでした。

どんな助けでも大歓迎です:)

4

2 に答える 2