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

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)

```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 )

{
//  printBins(current,requests);
}
return ;
}
else
{

getBins(requests, current, index+1 , bins);
getBins(requests, current, index+1 , bins);
}
}```

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.

每一个你不满意的现在，都有一个你没有努力的曾经。
一个历史类的公众号，欢迎关注