@ania
My idea is based on the post that i had replied in
http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b?hl=en#
A simple tweak to the above algo can be used to solve bin-packing
problem in a (probably) faster time. First, please go through the
above post.
The maximal possible subset problem says that we need to find all
subsets for the maximum sum that doesn't exceed "Wmax". Now, to
understand how it maps to the bin-packing problem you need to do the
following..
In bin-packing problem :
1) N maps to the no. of input elements.
2) Wmax maps to C, the capacity of a bin.
3) The no. of bins maps to finding the no. of unique subsets, i.e no
repeating element in any 2 subsets found, and the no. of such subsets
should be atleast >= no. of bins provided.
Hence, keeping the above things in mind all we need to do is:
a) Check if A[N, C] = 1, if this fails that means there is no
solution. If it is equal to 1, then there is possibility of uniquely
filling K bins of C capacity. (if 1, then goto step 2)
b) As you can see that while finding the no. of subsets an element can
occur in 2 different subsets, for eg- {a,b,c} and {a,b,d}. To generate
unique subsets we can take another array of size B[N, C] and
initialize it with 0. Now, whenever we find a valid subset by using
A[N,C] we will simultaneously mark the corresponding elements in B[N,
C] to 1. A value of 1 in B[N, C] will indicate that the element has
already been added and need not be traversed. Hence, while generating
more subsets we can check for B[i, j] to see if its 1, if yes then we
would skip/not-include it.
c) If we are able to generate atleast "K" unique subsets then we are
done.
Note: There might be slight modifications that you might need to make
apart from the above cited steps. In case, you feel that something is
missing please reply and let us know if the above algo works.
On Dec 11, 4:09 am, Ania <anka.step...@gmail.com> wrote:
> 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.
