我有一个数组，其中包含不同尺寸材料的列表：{4,3,4,1,7,8}。但是，该箱可以容纳最大 10 号的材料。我需要找出包装数组中所有元素所需的最小箱数。
对于上面的数组，你可以打包成 3 个 bin 并按如下方式划分它们：{4,4,1}, {3,7}, {8}. 还有其他可能的安排也适合三个备用管道，但不能用更少的
我试图通过递归来解决这个问题，以便更好地理解它。
我正在使用这个DP 公式（pdf 文件的第 20 页）
考虑具有 n = ∑nj 个项的输入 (n1;:::;nk)
确定可以打包到单个 bin 中的 k 元组（输入的子集）的集合
即所有元组 (q1;:::; qk) 其中 OPT(q1;:::;qk) = 1
用 Q 表示这个集合 对于每个 k 元组 q ，我们有 OPT(q) = 1
使用递归计算剩余值： 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);
}
}