实现背包的分支和绑定 [英] Implementing branch and bound for knapsack

问题描述

我很难实现这个（糟糕的）伪java代码（我想知道：为什么人们会这样做？）因为b& b背包问题。这是我到目前为止的实现，它最多输出80（当它应该打印90，对于教科书样本中的项目）。我创建了一个比较器（在LinkedList上），在将元素传递给算法之前，按Pi / Wi对元素进行排序，但此输入已经预先排序。我正在调试（并更新发布的代码），因为我猜这是一个数组索引问题......或者边界函数是否有错误？

I'm having a headache implementing this (awful) pseudo-java code (I wonder: why the hell people do that?) for the b&b knapsack problem. This is my implementation so far, which outputs a maximum of 80 (when it should print 90, for the items on the textbook sample). I created a Comparator (on a LinkedList) to sort the elements by Pi/Wi before passing them to the algorithm, but on this input is already presorted. I'm debugging right now (and updating the posted code), cause I guess it's an array indexing problem... or is there a mistake on the bounding function?

输入：

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

推荐答案

我只用给定的例子对它进行了测试，但看起来就像伪代码所说的那样

I have only tested it with the given example, but it looks like that wherever the pseudocode says

enqueue(Q, u)

你应该添加副本 u 到链接列表，而不是将引用传递给 u 并继续操作它。

you should add a copy of u to the linked list, rather than passing a reference to u and continue manipulating it.

换句话说，为类 Node 定义一个复制构造函数，然后执行

In other words, define a copy constructor for the class Node and do

Q.offer(new Node(u));

而不是

Q.offer(u);

实际上，上面给出的代码只分配了类的两个实例节点每次调用 branchAndBound（..）

In fact, the code you give above only allocates two instances of the class Node per call to branchAndBound(..)

这篇关于实现背包的分支和绑定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！