我有一个数组，其中包含不同大小的材料列表：{4,3,4,1,7,8}但是，垃圾箱可以容纳10号以下的材料。我需要找出将数组中的所有元素打包所需的最小容器数。
对于上面的数组，您可以打包到3个容器中，并按如下方式进行划分：{4,4,1}，{3,7}，{8}有其他可能的安排，也适合三个库存管，但不能少
我试图通过递归来解决这个问题，以便更好地理解它。
我正在使用dp公式（pdf文件的第20页）
考虑一个输入（n1；：：；nk）具有n=∑nj项
确定一组k元组（输入的子集），这些元组可以打包到单个bin中
也就是说，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 logn）时间内运行。
我建议您首先尝试nfdh：按降序排序，将结果存储在一个链接列表中，然后重复尝试从开始处开始插入项目（首先是最大值），直到您填满了bin或没有其他可插入的项目为止。然后去下一个垃圾箱等等。
参考文献：
Owen Kaser，Daniel Lemire，Tag-Cloud Drawing: Algorithms for Cloud Visualization，社会信息组织的标记和元数据（WWW 2007），2007年（相关讨论见第5.1节。）
例如，小科夫曼、M.R.加里、D.S.约翰逊和R.E.塔扬。面向层次的二维包装算法的性能界限。暹罗计算，9（4）：808-8261980。