实现背包的分支和绑定
对于b＆b背包问题，我很难实现这个（糟糕的）伪java代码 （我想知道：为什么人们会那么做？）。 这是我到目前为止的实现，它最多输出80（当它应该打印90，对于教科书样本中的项目）。 我创建了一个比较器（在LinkedList上），在将元素传递给算法之前，按Pi / Wi对元素进行排序，但此输入已经预先排序。 我正在调试（并更新发布的代码），因为我猜这是一个数组索引问题……或者边界函数是否有错误？
输入：
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 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 Q = new LinkedList(); 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.weightmaxProfit){ 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; } } } 我只用给定的例子对它进行了测试，但它看起来就像伪代码所说的那样
enqueue(Q, u)
你应该将u的副本添加到链表中，而不是将引用传递给u并继续操作它。
换句话说，为Node类定义一个复制构造函数
Q.offer(new Node(u));
代替
Q.offer(u);
实际上，上面给出的代码只会在每次调用branchAndBound(..)分配两个Node类实例branchAndBound(..)