A

#### Ania

Here is my problem:

I implemented recurive algorithm in c++ for a problem given below:

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.

I try to convert my recursive algorithm to an one. However, my

implementation with explicit stack doesn't work as I expected. I can't

pinpoint the place where I have made a mistake.

//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

*.sum() + items[index] + items.back() <=*

bin_capacity || bin_capacity - bins

bin_capacity || bin_capacity - bins

*.sum() == items[index])*

{

bins{

bins

*.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(binsreturn 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

*);*

}

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]-

stack.push(child_node);

}

}

item_index++;

}

else

{

if (node.bins() == BINS)

{

//copy solution

bins = node.bins;

return true;

}

}

}

return false;

}

Any help would be highly appreciated.}

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 help would be highly appreciated.