Bin Packing - 蛮力递归解决方案 - 如何使其更快

Question

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

对于上述阵列中,可以在3个箱包装和将它们划分如下:{4,4,1},{3,7},{8}.还有其他可能的安排也适合三个库存管道,但它不能用更少的

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

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

考虑输入(n1; :::; nk),其中n =Σnj项
确定可以打包到单个bin中的k元组(输入的子集)的集合
即所有元组(q1; :::; qk)其中OPT(q1; :::; qk)= 1
用Q表示这个集合对于每个k元组q,我们有OPT(q)= 1
通过使用递归计算剩余值: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);
        }
}

Answer 1

动态编程算法是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: 2007年社会信息组织(WWW 2007)的云可视化,标记和元数据算法.(相关讨论见5.1节)

EG Coffman,Jr.,MR Garey,DS Johnson和RE Tarjan.面向水平的二维打包算法的性能界限.SIAM J. Comput.,9(4):808-826,1980.