我在为 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<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;
}
}
}