@ania,
I think there is a faster way to solve the bin-tracking problem... i
have an idea, in case you want to discuss it do reply...
On Dec 3, 3:28 am, Ania <anka.step...@gmail.com> wrote:
> 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.
