Guys, if you can find a solution that is not exponential time in the worst case you are going to be famous because this problem is NP-Hard in the strong sense. I.e. there is not even a pseudo-polynomial time algorithm. To get a perfect solution every time, you can't do better than heuristic search, and the search might take a very long time to find an optimal answer.
http://en.wikipedia.org/wiki/Bin_packing_problem gives some bounds on how bad the solution can get if you use the standard heuristics: First fit and best fit. They also mention your sorting strategy there. A method that works well in practice is to implement first fit and best fit and then keep reordering the input with a random permutation generator, trying first and best fit on each permutation, keeping track of what you've tried so far so as not to duplicate work (although if N is large, this is a waste of time because the number of permutations is N!) and the best result. With this method, you can set a timer and always have a result when the timer expires. A more scientific variation on this is simulated annealing, which I'll let you look up. It's not clear that SA will do better than the simple randomization above, however. Backtracking alone is probably not a good idea because it explores the search space depth first. If it makes a bad decision early on, there may not be enough nanoseconds in the life of the universe for it ever to backtrack far enough to undo the damage. Cheers. On Dec 12, 1:13 pm, Lucifer <sourabhd2...@gmail.com> wrote: > A slightly different approach on the lines of data access and ease of > understanding: > > 1) Sort the input array i.e the weights array W[N] . > 2) Identify the no. of unique elements in it and create the following: > a) Count[R] - count of each unique element based on its sorted > order. > // Maintain a copy of Count[R] to used later for > generating the unique subsets. Say, "DupCount[R]" > > b) A[R, C] - the array used for solving the bin-packing (or the > maximal subset problem) > > c) W[R] - the unique sorted weight array > > Here, R is the no. of unique elements. > > Now, the recurrence relation will get modified as follows: > > A[i , j] = A[i-1, j] or ( Count[i] != 0 ? { A[ i, j - W[i] ] ; -- > Count[i] ;} : A[ i-1 , j - W[i] ] ) > > ---------------------------------------- > > While generating the unique subsets we won't need a second array (B[N, > C]) as explained in the previous post. All we need to do is whenever > we add an element to the subset we will decremented the corresponding > count in array "DupCount[R]". If the value of "DupCount[i]" at any > instance becomes 0, then that means that usage of that particular > unique element is exhausted. > > On Dec 12, 4:54 pm, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > @ania > > > My idea is based on the post that i had replied > > inhttp://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea0... > > > 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.- Hide quoted text - > > - Show quoted text - -- 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.
