分支绑定背包实现中的内存阻塞

Question

我基于 来自此处的伪 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<Item> 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<Node> PQ = new PriorityQueue<Node>(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 <=W && u.profit > 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;
    }

}



}

Answer 1

我得到了一个稍微更快的实现，用泛型去掉了所有 Collection 实例，而是使用数组。

Answer 2

不确定您是否仍然需要深入了解算法，或者您的调整是否已经解决了您的问题，但是使用像您实现的那样的广度优先分支定界算法，总是有可能出现内存使用问题。当然，您希望能够排除足够数量的分支，以保持优先级队列中的节点数量相对较小，但在最坏的情况下，您最终可能会与内存中背包中项目选择的可能排列一样多的节点。当然，最坏的情况是极不可能的，但对于大型问题实例，即使是普通的树也可能最终会用数百万个节点填充优先级队列。

如果您要在代码中抛出许多不可预见的大型问题实例，并且需要记住，无论算法必须考虑多少个分支，您都不会耗尽内存，我会考虑深度优先分支定界算法，如本书第 2.5.1 节中概述的 Horowitz-Sahni 算法：http://www.or.deis.unibo.it/knapsack.html。对于某些问题实例，这种方法在找到最佳解决方案之前必须考虑的可能解决方案的数量方面效率较低，但对于某些问题实例，它会更有效——这实际上取决于结构树的。