分支和绑定背包实现的内存扼流圈
我从这里开始编写基于伪Java代码的分支和绑定背包算法的实现。 不幸的是，这个问题的大型实例会让内存窒息。 为什么是这样？ 如何使此实现更节省内存？
链接上文件的输入格式如下：
numberOfItems maxWeight profitOfItem1 weightOfItem1 . . . profitOfItemN weightOfItemN // http://books.google.com/books?id=DAorddWEgl0C&pg=PA233&source=gbs_toc_r&cad=4#v=onepage&q&f=true import java.util.Comparator; import java.util.LinkedList; import java.util.PriorityQueue; class ItemComparator implements Comparator { public int compare (Object item1, Object item2){ Item i1 = (Item)item1; Item i2 = (Item)item2; if ((i1.valueWeightQuotient)<(i2.valueWeightQuotient)) return 1; if ((i2.valueWeightQuotient)<(i1.valueWeightQuotient)) return -1; else { // costWeightQuotients are equal if ((i1.weight)<(i2.weight)){ return 1; } if ((i2.weight)<(i1.weight)){ return -1; } } return 0; } }
class Node { int level; int profit; int weight; double bound; } class NodeComparator implements Comparator { public int compare(Object o1, Object o2){ Node n1 = (Node)o1; Node n2 = (Node)o2; if ((n1.bound)<(n2.bound)) return 1; if ((n2.bound)<(n1.bound)) return -1; return 0; } } class Solution { long weight; long value; } public class BranchAndBound { static Solution branchAndBound2(LinkedList items, double W) { double timeStart = System.currentTimeMillis(); 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; Node v = new Node(); // tree root int maxProfit=0; int usedWeight=0; NodeComparator nc = new NodeComparator(); PriorityQueue PQ = new PriorityQueue(n,nc); v.level=-1; v.profit=0; v.weight=0; // v initialized to -1, dummy root v.bound = bound(v,W, n, w, p); PQ.add(v); while(!PQ.isEmpty()){ v=PQ.poll(); u = new Node(); if(v.bound>maxProfit){ // check if node is still promising u.level = v.level+1; // set u to the child that includes the next item u.weight = v.weight + w[u.level]; u.profit = v.profit + p[u.level]; if (u.weight maxProfit){ maxProfit = u.profit; usedWeight = u.weight; } u.bound = bound(u, W, n, w, p); if(u.bound > maxProfit){ PQ.add(u); } u = new Node(); u.level = v.level+1; u.weight = v.weight; // set u to the child that does not include the next item u.profit = v.profit; u.bound = bound(u, W, n, w, p); if(u.bound>maxProfit) PQ.add(u); } } Solution solution = new Solution(); solution.value = maxProfit; solution.weight = usedWeight; double timeStop = System.currentTimeMillis(); double elapsedTime = timeStop - timeStart; System.out.println("* Time spent in branch and bound (milliseconds):" + elapsedTime); return solution; } static double bound(Node u, double W, int n, int [] w, int [] p){ int j=0; int k=0; int totWeight=0; double result=0; if(u.weight>=W) return 0; else { result = u.profit; totWeight = u.weight; // por esto no hace if(u.level < w.length) { j= u.level +1; } int weightSum; while ((j < n) && ((weightSum=totWeight + w[j])<=W)){ totWeight = weightSum; // 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 excluded kth item } return result; } } }
我得到了一个稍微快一点的实现，带走了generics的所有Collection实例，而不是使用数组。
不确定你是否仍然需要深入了解算法或者你的调整是否已经解决了你的问题，但是使用广度优先的分支和绑定算法，就像你实现的算法一样，总是存在内存使用问题的可能性。 当然，您希望能够排除足够数量的分支以保持优先级队列中的节点数量相对较小，但在最坏的情况下，您可能最终会具有尽可能多的节点，因为存储器中保存的背包中可能存在项目选择的排列。 当然，最糟糕的情况是极不可能的，但对于大型问题实例，即使是普通的树也可能最终填充数百万个节点的优先级队列。
如果你要在你的代码中抛出大量无法预料的大问题实例，并且需要知道无论算法必须考虑多少分支你都永远不会耗尽内存，我会考虑一个深度优先分支和绑定算法，如本书第2.5.1节中概述的Horowitz-Sahni算法： http ： //www.or.deis.unibo.it/knapsack.html 。 对于某些问题实例，这种方法在找到最优解决方案之前必须考虑的可能解决方案的数量方面效率较低，但对于某些问题实例，它将更有效 – 它实际上取决于结构树的