2

I implemented backtracking based solution for my problem which I specified in my previous post: Packing items into fixed number of bins

(Bin is a simple wrapper for vector<int> datatype with additional methods such as sum() )

bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned index, unsigned bin_capacity)
{
    if (bin_capacity - items.front() < 0) return false;

    if (index < items.size())
    {
        //try to put an item into all opened bins
        for(unsigned i = 0; i < bins.size(); ++i)
        {
            if (bins[i].sum() + items[index] + items.back() <= bin_capacity || bin_capacity - bins[i].sum() == items[index])
            {
                bins[i].add(items[index]);
                return backtrack(items, bins, index + 1, bin_capacity);

            }
        }
        //put an item without exceeding maximum number of bins
        if (bins.size() < BINS)
        {
            Bin new_bin = Bin();
            bins.push_back(new_bin);
            bins.back().add(items[index]);

            return backtrack(items, bins, index + 1, bin_capacity);

        }
    }
    else
    {
        //check if solution has been found
        if  (bins.size() == BINS )
        {
            for (unsigned i = 0; i <bins.size(); ++i)
            {
                packed_items.push_back(bins[i]);
            }

            return true;
        }
    }
    return false;
}

Although this algorithm works quite fast, it's prone to stack overflow for large data sets.

I'm looking for any ideas and suggestions how to improve it.

Edit:

I decided to try an iterative approach with explicit stack, but my solution doesn't work as expeced - sometimes it gives incorrect results.

bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned index, unsigned bin_capacity)
{
      stack<Node> stack;
      Node node, child_node;
      Bin new_bin;
      //init the stack
      node.bins.add(new_bin);
      node.bins.back().add(items[item_index]);
      stack.push(node);
      item_index++;

      while(!stack.empty())
      {
        node = stack.top();
        stack.pop();

        if (item_index < items.size())
        {
            if (node.bins.size() < BINS)
            {
               child_node = node;
               Bin empty;
               child_node.bins.add(empty);
               child_node.bins.back().add(items[item_index]);
               stack.push(child_node);
            }

            int last_index = node.bins.size() - 1;
            for (unsigned i = 0; i < node.bins.size(); i++)
            {
                if (node.bins[last_index - i]->get_sum() + items[item_index]+ items.back() <= bin_capacity || 
                bin_capacity - node.bins[last_index - i]->get_sum() == items[item_index]) 
               {
                   child_node = node;
                   child_node.bins[last_index - i]->push_back(items[item_index]);
                   stack.push(child_node);
                }
            }
            item_index++;
            }
        else
        {
           if (node.bins() == BINS)
           {
               //copy solution
               bins = node.bins;
               return true;
           }
       }
   }
    return false;
}

Any suggestions are highly appreciated.

Community
  • 1
  • 1
solitaire
  • 93
  • 1
  • 5
  • 1
    In the interest of avoiding stack overflows, you may want to attempt an iterative approach. – Rob Nov 11 '11 at 18:54
  • @robjb: though possible, usually backtracking algorithms are transfered into iterative algorithms not trivially, and the iterative solution must consist a stack [or an equivalent powerful data structure] as well. – amit Nov 11 '11 at 19:36
  • @amit: very true... I would not suggest that doing so is trivial. It may be a worthwhile attempt if the goal is to reduce overflows, but I expect it will be a trade-off between performance & safety. – Rob Nov 11 '11 at 19:49
  • @amit if you do use an explicit stack, you can control the maximum size, as opposed to the function call stack which can be unpredictable. – jli Nov 13 '11 at 03:25
  • @robjb After a long break from my problem, I decided to implement an iterative solution. However, it doesn't work as I expected. – solitaire Dec 02 '11 at 16:23

1 Answers1

1

I think there's a dynamic programming algorithm for solving the multiple-bin packing problem, or at least, a polynomial approximation algorithm. Take a look here and here.

Óscar López
  • 232,561
  • 37
  • 312
  • 386