Databases
StackOverflow2013
Postsdbo
POBin Packing - Brute force recursive solution - How to make it faster
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBin Packing - Brute force recursive solution - How to make it faster
    text
    copied!<p>I have an array which contains a list of different sizes of materials : <code>{4,3,4,1,7,8}</code> . However, the bin can accomodate materials upto size 10. I need to find out the minimum number of bins needed to pack all the elements in the array.</p> <p>For the above array, you can pack in 3 bins and divide them as follows: <code>{4,4,1}</code>, <code>{3,7}</code> , <code>{8}</code> . There are other possible arrangements that also fit into three stock pipes, but it cannot be done with fewer</p> <p>I am trying to solve this problem through recursion in order to understand it better.</p> <p>I am using <a href="http://algo2.iti.kit.edu/appol/les7.pdf" rel="nofollow">this</a> DP formulation (page 20 of the pdf file)</p> <blockquote> <p>Consider an input (n1;:::;nk) with n = ∑nj items<br> Determine set of k-tuples (subsets of the input) that can be packed into a single bin<br> That is, all tuples (q1;:::;qk) for which OPT(q1;:::;qk) = 1<br> Denote this set by Q For each k-tuple q , we have OPT(q) = 1<br> Calculate remaining values by using the recurrence : OPT(i1;:::;ik) = 1 + minOPT(i1 - q1;:::;ik - qk)</p> </blockquote> <p>I have made the code, and it works fine for small data set. But if increase the size of my array to more than 6 elements, it becomes extremely slow -- <strong>takes about 25 seconds to solve an array containing 8 elements</strong> Can you tell me if theres anything wrong with the algorithm? I dont need an alternative solution --- <strong>just need to know why this is so slow, and how it can be improved</strong></p> <p>Here is the code I have written in C++ :</p> <pre><code>void recCutStock(Vector&lt;int&gt; &amp; requests, int numStocks) { if (requests.size() == 0) { if(numStocks &lt;= minSize) { minSize = numStocks; } // cout&lt;&lt;"GOT A RESULT : "&lt;&lt;numStocks&lt;&lt;endl; return ; } else { if(numStocks+1 &lt; minSize) //minSize is a global variable initialized with a big val { Vector&lt;int&gt; temp ; Vector&lt;Vector&lt;int&gt; &gt; posBins; getBins(requests, temp, 0 , posBins); // 2-d array(stored in posBins) containing all possible single bin formations for(int i =0; i &lt; posBins.size(); i++) { Vector&lt;int&gt; subResult; reqMinusPos(requests, subResult, posBins[i]); // subtracts the initial request array from the subArray //displayArr(subResult); recCutStock(subResult, numStocks+1); } } else return; } } </code></pre> <p>The getBins function is as follows : </p> <pre><code>void getBins(Vector&lt;int&gt; &amp; requests, Vector&lt;int&gt; current, int index, Vector&lt;Vector&lt;int&gt; &gt; &amp; bins) { if (index == requests.size()) { if(sum(current,requests) &lt;= stockLength &amp;&amp; sum(current, requests)&gt;0 ) { bins.add(current); // printBins(current,requests); } return ; } else { getBins(requests, current, index+1 , bins); current.add(index); getBins(requests, current, index+1 , bins); } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload