Hi,
Here is my problem:
I have a list of items (only positive integers are allowed) and fixed
number of bins of identical capacity. I need to pack items (if
possible) so that elements in each bin sum up to given capacity.
So far I implemented recursive algorithm but I try to convert my
recursive algorithm to an iterative one. However, my implementation
with explicit stack doesn't work as I expected.
//items are sorted in decreasing order
Recursive:
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;
}
Iterative( not working properly)
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 <= last_index; 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 would be highly appreciated.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
