Tag: 分支定界

实现背包的分支和绑定

对于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= […]