algorithm – Bin Packing – 强力递归解决方案 – 如何使其更快

我有一个数组,其中包含不同大小的材料列表:{4,3,4,1,7,8}.但是,垃圾箱可以容纳最大尺寸为10的材料.我需要找出包装阵列中所有元素所需的最小垃圾箱数量.

对于上面的数组,您可以打包3个箱子并按如下方式划分:{4,4,1},{3,7},{8}.还有其他可能的安排也适合三个库存管道,但它不能用更少的

我试图通过递归来解决这个问题,以便更好地理解它.

我正在使用this DP配方(pdf文件的第20页)

Consider an input (n1;:::;nk) with n = ∑nj items
Determine set of k-tuples (subsets of the input) that can be packed into a single bin
That is, all tuples (q1;:::;qk) for which OPT(q1;:::;qk) = 1
Denote this set by Q For each k-tuple q , we have OPT(q) = 1
Calculate remaining values by using the recurrence : OPT(i1;:::;ik) = 1 +
minOPT(i1 – q1;:::;ik – qk)

我已经制作了代码,它适用于小型数据集.但是如果将我的数组的大小增加到超过6个元素,它变得非常慢 – 解决包含8个元素的数组需要大约25秒你能告诉我算法是否有问题?我不需要替代解决方案—只需要知道为什么这么慢,以及如何改进它

这是我用C编写的代码:

void recCutStock(Vector<int> & requests,  int numStocks)
{
 if (requests.size() == 0)
 {

     if(numStocks <= minSize)
    {
        minSize = numStocks;

    }
//   cout<<"GOT A RESULT : "<<numStocks<<endl;
        return ;
 }
 else
 {
    if(numStocks+1 < minSize) //minSize is a global variable initialized with a big val
    {
     Vector<int> temp ; Vector<Vector<int> > posBins;
     getBins(requests, temp, 0 , posBins); // 2-d array(stored in posBins) containing all possible single bin formations

    for(int i =0; i < posBins.size(); i++)
    {
        Vector<int> subResult;
        reqMinusPos(requests, subResult,  posBins[i]);  // subtracts the initial request array from the subArray
        //displayArr(subResult);


            recCutStock(subResult,  numStocks+1);


    }
    }
    else return;
 }

}

getBins函数如下:

void getBins(Vector<int> & requests, Vector<int> current, int index, Vector<Vector<int> > & bins)

{

if (index == requests.size())

{

if(sum(current,requests) <= stockLength && sum(current, requests)>0 )

        {
                bins.add(current);
            //  printBins(current,requests);
            }
            return ;
        }
        else
        {

        getBins(requests, current, index+1 , bins);
                current.add(index);
            getBins(requests, current, index+1 , bins);
        }
}
动态编程算法是O(n ^ {2k}),其中k是不同项的数量,n是项的总数.无论实施如何,这都可能非常缓慢.通常,在解决NP难问题时,速度需要启发式算法.

我建议你考虑Coffman等人的Next Fit Decreasing Height(NFDH)和First Fit Decreasing Height(FFDH).它们分别是2最优和17/10最优,并且它们在O(n log n)时间内运行.

我建议你先尝试NFDH:按递减顺序排序,将结果存储在一个链表中,然后反复尝试从头开始插入项目(最大值为第一个),直到你填满垃圾箱或没有更多的项目可以插入.然后转到下一个垃圾箱,依此类推.

参考文献:

Owen Kaser,Daniel Lemire,Tag-Cloud Drawing: Algorithms for Cloud Visualization,社会信息组织标签和元数据(WWW 2007),2007.(相关讨论见5.1节)

E. G. Coffman,Jr.,M.R. Garey,D.S. Johnson和R. E. Tarjan.面向水平的二维打包算法的性能界限. SIAM J. Comput.,9(4):808-826,1980.

相关文章
相关标签/搜索