Hi,
I'm really interested in your idea as my solution is probably far from
being optimal.
On 11 Gru, 00:00, Lucifer <sourabhd2...@gmail.com> wrote:
> @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.
