@atul.. Its an explanation of the logic not the actual code... You can use the following code to implement the same..
A[i,j] = A[i-1, j]; if ( A[i, j] == 0 and j - W[i] >=0) A[i, j] = A[i -1, j - W[i]]; On Jan 7, 9:45 pm, atul anand <atul.87fri...@gmail.com> wrote: > @Lucifer : thats ok....but you are using bitwise OR to fill up the array > A[]. > if condition does not fullfill then wat to do to fill A[i,j] ?? > > i guess take it 0 if it does not fullfill.. > > A[i , j] = A[i-1, j] | 0 // A[ i-1 , j - W[i] ] check fail > > i didnt read your whole algorithm so i am taking this assumption , correct > me if i am wrong > > > > > > > > On Sat, Jan 7, 2012 at 10:03 PM, Lucifer <sourabhd2...@gmail.com> wrote: > > @atul.. > > > I thought that check would be obvious as i didn't put in the code.. so > > when the code is written for the second option we need to also check > > for j-W[i] >=0.. > > :)... > > > On Jan 7, 9:15 pm, atul007 <atul.87fri...@gmail.com> wrote: > > > @Lucifier: > > > > i guess you made some editing mistake :- > > > > 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 // it shoud be 1 for 0 <= i <=N > > > > about this equation :- > > > > A[i , j] = A[i-1, j] | A[ i-1 , j - W[i] ] > > > > say if W[i]=10 and j=3 , i =2; > > > then it would be accessing A[1][3-10] i.e A[1][-7] ..... dat would be > > > wrong. > > > > On Dec 7 2011, 6:40 pm, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > I have modified some part of the above post below to avoid confusion > > > > regarding the generation of all subsets: > > > > > Say, we need to find all the subsets which led to A[N, K] = 1, to do > > > > this we will take the following steps : > > > > > a) If ( i == 0 ) print the subset and return. > > > > > b) if A[N -1 , K] = 1, > > > > b1) then W[N] doesn't belong to the subset , continue > > > > recursively ( goto step a). > > > > b2) goto step c. > > > > else goto step c. > > > > > c) if A[N -1 , K - W[N] ] = 1, then W[N] belongs to the subset , > > > > continue recursively ( goto step a) . > > > > else return. > > > > > On Dec 7, 6:29 pm, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > > 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. -- 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.
