I have an idea, i think it can be done in O(N * Wmax). Let the weight array be W[N].
Take an array A[N][Wmax] , where N is the no. of weights provided and Wmax is the max weight. Initialize the array with the following values, 1) A[0, j] = 0 for 1 <= j <= Wmax 2) A[i, 0] = 1 for 0 <= i <= Wmax Now, if an A[i , j] = 1, that means using the first "i" weights it is possible pick a subset whose sum is "j", else if A[i , j] = 0, then it not possible to have subset of first "i" weights whose sum would sum up to "j". Now, to solve the above problem we can use the following equation, A[i , j] = A[i-1, j] or A[ i-1 , j - W[i] ] Using the above equation calculate all values A[i, j] where 1 <= i <= N and 1 <= j <= Wmax. Now, Scan A[N, j] from right to left ( Wmax >= j >= 0 ) till you get a value of 1, let the found column index be "K". A[N, K] = 1, basically signifies the maximum sum that you can make which is "K". Now that you have the maximum sum <= Wmax which can be made i.e "K", the next problem will be 2 figure all the subsets. To find all the subsets backtrack based on the equation given above and record the weights for which A[i, j] = 1, i.e. Say, we need to find all the subsets which led to A[N, K] = 1, to do this we will check for, a) if A[N -1 , K] = 1, then W[N] doesn't belong to the subset , continue recursively. b) if A[N -1 , K - W[N] ] = 1, then W[N] belongs to the subset , continue recursively. Hence, To find the max value it will take O( N * Wmax) + O( Wmax) To find all the subsets, it will take O( X * Y) where, x is the no. of subsets and y is the average no. of elements in it. On Dec 5, 5:09 pm, Shashank Narayan <shashank7andr...@gmail.com> wrote: > @piyuesh 3-Sum is not exponential ? its quadratic , check wiki for refrence > ? > > On Mon, Dec 5, 2011 at 5:36 PM, Piyush Grover > <piyush4u.iit...@gmail.com>wrote: > > > > > > > > > > > As I mentioned earlier solution with exponential time-complexity is the > > obvious one. Is there any way to solve this problem by greedy/Dynamic algo? > > > On Mon, Dec 5, 2011 at 5:24 PM, WgpShashank > > <shashank7andr...@gmail.com>wrote: > > >> @piyuesh , Saurabh isn't 3-Sum Suffics Here ? > > >> Another thought problem can also be thought by generating power set of > >> given set e.g. if set has n elemnts its power set has 2^n elements , then > >> finds the set that has sum up yo given weight isn't it ? hope you know how > >> to find power set efficiently ? > > >> correct if is missed anything ? > > >> Thanks > >> Shashank > >> Computer Science > >> BIT Mesra > >>http://www.facebook.com/wgpshashank > >>http://shashank7s.blogspot.com/ > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To view this discussion on the web visit > >>https://groups.google.com/d/msg/algogeeks/-/a9F-gPQkjm0J. > > >> 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. > > > -- > > 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. > > * > ** > * -- 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.
