@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 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 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
> > wrote:
>
> > > @piyuesh 3-Sum is not exponential ? its quadratic , check wiki for
> > > refrence
> > > ?
>
> > > On Mon, Dec 5, 2011 at 5:36 PM, Piyush Grover
> > > 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
> > > > 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
