4

私は、b&b ナップザックの問題のために、この (ひどい) 疑似 Java コードを実装することに頭を悩ませています(私は疑問に思います: なぜ人々はそんなことをするのでしょうか?)。これはこれまでの私の実装で、最大 80 を出力します (教科書サンプルの項目の場合、90 を出力する必要があります)。要素をアルゴリズムに渡す前に Pi/Wi で並べ替える Comparator (LinkedList 上) を作成しましたが、この入力では既に並べ替え済みです。私は今デバッグ中です（そして投稿されたコードを更新しています）、それは配列のインデックス付けの問題だと思います...または境界関数に間違いがありますか？

入力：

4 16 //# items maxWeight
40 2 // profit weight
30 5
50 10
10 5


class Node
{
    int level;
    int profit;
    int weight;
    double bound;

}

public class BranchAndBound {
    static int branchAndBound (LinkedList<Item> items, int W) {
        int n = items.size();

        int [] p= new int[n];
        int [] w= new int[n];

        for (int i=0; i<n;i++){

            p [i]= (int)items.get(i).value;
            w [i]= (int)items.get(i).weight;

        }

        Node u = new Node();
        Node v = new Node(); // tree root

        int maxProfit=0;

        LinkedList <Node> Q = new LinkedList<Node>();

        v.level=-1;
        v.profit=0;
        v.weight=0; // v initialized to -1, dummy root

        Q.offer(v); // place the dummy at the root

        while(!Q.isEmpty()){
            v = Q.poll();

            if (v.level==-1){
              u.level=0;
            }
            else if(v.level != (n - 1))
            {
               u.level = v.level+1; // set u to be a child of v
            }

            u = new Node();
            u.weight = v.weight + w[u.level];// set u to the child
            u.profit = v.profit + p[u.level]; // that includes the
                                             //next item
            double bound = bound(u, W, n, w, p);
            u.bound=bound;

            if(u.weight<=W && u.profit>maxProfit){
                maxProfit = u.profit;
            }

            if(bound>maxProfit){
                Q.add(u);
            }

            u = new Node();
            u.weight = v.weight; // set u to the child that
            u.profit = v.profit;// does NOT include the next item

            bound = bound(u, W, n, w, p);
            u.bound = bound;

            if (bound>maxProfit){
                Q.add(u);
            }
        }

        return maxProfit;
    }

    public static float bound(Node u, int W, int n, int [] w, int [] p){
        int j=0; int k=0;
        int totWeight=0;
        float result=0;

        if(u.weight>=W)
            return 0;
        else {
            result = u.profit;
            j= u.level +1;
            totWeight = u.weight;

            while ((j < n) && (totWeight + w[j]<=W)){
                totWeight = totWeight + w[j]; // grab as many items as possible
                 result = result + p[j];
                j++;
            }
            k=j; // use k for consistency with formula in text
            if (k<n)
                result = result + (W-totWeight) * p[k]/w[k];// grab fraction of kth item

            return result;
        }
    }
}
4

1 に答える 1

3

与えられた例でのみテストしましたが、疑似コードが言うところならどこでもそのように見えます

enqueue(Q, u)

参照を渡して操作を続けるのではなく、リンクされたリストにのコピーを追加する必要があります。uu

つまり、クラスのコピー コンストラクターを定義しNode、

Q.offer(new Node(u));

それ以外の

Q.offer(u);

Node実際、上記のコードは、呼び出しごとにクラスの 2 つのインスタンスを割り当てるだけです。branchAndBound(..)

于 2011-09-16T20:09:00.253 に答える