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

我有一个数组，其中包含不同大小的材料列表：{4,3,4,1,7,8}。但是，该箱子最多可容纳 10 号材料。我需要找出包装数组中所有元素所需的最小箱子数量。

对于上面的数组，你可以打包成 3 个 bin，并按如下方式划分它们：{4,4,1}, {3,7} , {8}。还有其他可能的布置也适合三个库存管，但不能用更少的数量来完成

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

我在用thisDP 配方（pdf 文件第 20 页）

考虑输入 (n1;:::;nk)，其中 n = Σnj 个项目
确定可以打包到单个 bin 中的 k 元组集（输入的子集）
即，所有 OPT(q1;:::;qk) = 1 的元组 (q1;:::;qk)
用 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);
        }
}

动态规划算法为 O(n^{2k})，其中 k 是不同项目的数量，n 是项目的总数。无论实施如何，这都可能非常慢。通常，在解决 NP 难题时，需要启发式方法来提高速度。

我建议您考虑 Coffman 等人的下一次适应递减高度 (NFDH) 和首次适应递减高度 (FFDH)。它们分别是 2 最优和 17/10 最优，并且运行时间为 O(n log n)。

我建议您首先尝试 NFDH：按降序排序，将结果存储在链接列表中，然后重复尝试从头开始插入项目（首先是最大值），直到填满垃圾箱或没有更多项目可以插入被插入。然后转到下一个垃圾箱，依此类推。

参考:

欧文·凯瑟、丹尼尔·莱米尔、标签云绘图：云可视化算法，社会信息组织的标签和元数据 (WWW 2007)，2007 年。（有关相关讨论，请参阅第 5.1 节。）

E. G. Coffman, Jr.、M. R. Garey、D. S. Johnson 和 R. E. Tarjan。面向级别的二维打包算法的性能界限。 SIAM J. 计算机，9(4)：808–826，1980。