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

Question

我有一个包含不同尺寸 Material 列表的数组:{4,3,4,1,7,8}。但是，垃圾箱最多可容纳 10 号 Material 。我需要找出包装阵列中所有元素所需的最少垃圾箱数量。

对于上面的数组，可以打包成3个bin，分别为:{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 个元素，它会变得非常慢 -- 大约需要 25 秒来解决包含 8 个元素的数组你能告诉我这个算法有什么问题吗？我不需要替代解决方案 --- 只需要知道为什么这么慢，以及如何改进它

这是我用 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-hard 问题时，需要启发式方法来提高速度。

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

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

引用:

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.