Re: [algogeeks] Re: Maximal possible subsets Algorithm
@Piyush:.. nope is not correct ...
this is right
0 1 2 3
0 1 0 0 0
1 1 0 1 0
2 1 0 1 0
3 1 0 1 0
4 1 0 1 0
use this code to precompute..
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 Tue, Jan 10, 2012 at 1:05 PM, Piyush Grover wrote:
> How to create the lookup table?
> say if I have W = {2, 4, 6, 8} and Wmax = 3
>
> 0 1 2 3
> 0 1 0 0 0
> 1 1 1 1 0
>
> 2 1 1 1 1
> 3 1 1 1 1
> 4 1 1 1 1
>
> Is this correct???
>
>
> On Mon, Jan 9, 2012 at 2:55 PM, Lucifer wrote:
>
>> @All
>>
>> The same algo will work for both +ve and -ve nos.. no need for
>> modification..
>>
>> For ex-
>> Say the sum is 4 and the set is { 1, 2, 3, -2 }
>>
>> Now if u include -2 as part of ur solution then for the rest 3
>> elements the sum would be 4-(-2) = 6, which is correct...
>>
>>
>> On Jan 9, 2:20 pm, Siddhartha wrote:
>> > yup...that was what i was thinking... i guess for negative nos, we can
>> > define Wmax= sum of modulus of weights,and then the same algo works...
>>
>> --
>> 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.
Re: [algogeeks] Re: Maximal possible subsets Algorithm
How to create the lookup table?
say if I have W = {2, 4, 6, 8} and Wmax = 3
0 1 2 3
0 1 0 0 0
1 1 1 1 0
2 1 1 1 1
3 1 1 1 1
4 1 1 1 1
Is this correct???
On Mon, Jan 9, 2012 at 2:55 PM, Lucifer wrote:
> @All
>
> The same algo will work for both +ve and -ve nos.. no need for
> modification..
>
> For ex-
> Say the sum is 4 and the set is { 1, 2, 3, -2 }
>
> Now if u include -2 as part of ur solution then for the rest 3
> elements the sum would be 4-(-2) = 6, which is correct...
>
>
> On Jan 9, 2:20 pm, Siddhartha wrote:
> > yup...that was what i was thinking... i guess for negative nos, we can
> > define Wmax= sum of modulus of weights,and then the same algo works...
>
> --
> 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.
[algogeeks] Re: Maximal possible subsets Algorithm
@All
The same algo will work for both +ve and -ve nos.. no need for
modification..
For ex-
Say the sum is 4 and the set is { 1, 2, 3, -2 }
Now if u include -2 as part of ur solution then for the rest 3
elements the sum would be 4-(-2) = 6, which is correct...
On Jan 9, 2:20 pm, Siddhartha wrote:
> yup...that was what i was thinking... i guess for negative nos, we can
> define Wmax= sum of modulus of weights,and then the same algo works...
--
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.
[algogeeks] Re: Maximal possible subsets Algorithm
yup...that was what i was thinking... i guess for negative nos, we can define Wmax= sum of modulus of weights,and then the same algo works... -- 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.
Re: [algogeeks] Re: Maximal possible subsets Algorithm
@Siddhartha : i dont think so this will work for -ve number because we are doing A[ i - 1, j - W[i] ] so if W[i] is -ve number then it would increases Wmax which is the number of column. i guess same algo can be modified so as to make it work for -ve number. On Mon, Jan 9, 2012 at 2:23 PM, Siddhartha wrote: > @lucifer and others: does this work for negative elements? What to do > then??? > > -- > 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.
[algogeeks] Re: Maximal possible subsets Algorithm
@lucifer and others: does this work for negative elements? What to do then??? -- 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.
Re: [algogeeks] Re: Maximal possible subsets Algorithm
@Lucifer : got it ..nice and clear :) :).
On Sun, Jan 8, 2012 at 10:05 AM, Lucifer wrote:
> @atul..
>
> The table is used to record the state of subsets not print them.. (I
> am assuming that's what u meant)..Hence keeping that in mind, yes it
> captures all subsets... Now once A[N, K] is 1 that means there are
> some subsets whose sum will be equal to K. Hence, to find all such
> subsets we will backtrack accordingly...
>
> --
> A[i,j] -> Whether using first 'i' items a sum of 'j' can be made.. A
> value of 0/1 indicates whether its possible or not...
>
> Now there are 2 ways we can make a subset having sum j..
> 1) Consider that W[i] is part of the subset, then A[ i - 1, j - W[i] ]
> should be 1.
>// Hence while generating the subsets if A[i -1, j - W[i] ] = A[i,
> j] =1 , then W[i] will be part of subset... Point to be noted - the
> part of "that subset" which will be generated using the path whose
> intermediate nodes are (A[i, j] , A[i-1, j - W[i]])
>
> 2) Say 'i'th element doesn't contribute to the subset. Hence for A[i,
> j] to be 1, A[i-1, j] should be 1.
>// Hence when A[i-1, j] = A[i, j] = 1, then W[i] won't be a part
> of the subset... Point to be noted - the part of "that subset" which
> will be generated using the path whose intermediate nodes are (A[i,
> j] , A[i-1, j])
>
> -
>
>
> On Jan 7, 11:37 pm, atul anand wrote:
> > @Lucifer :
> >
> > for W[]={1,3,2,1,2} and Wmax=4.
> > this array will be formed.
> >
> > 0
> >
> > 1
> >
> > 2
> >
> > 3
> >
> > 4
> >
> > 0
> >
> > 1
> >
> > 0
> >
> > 0
> >
> > 0
> >
> > 0
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 0
> >
> > 0
> >
> > 0
> >
> > 3
> >
> > 1
> >
> > 1
> >
> > 0
> >
> > 1
> >
> > 1
> >
> > 2
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 2
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > 1
> >
> > is it printing all subset ?? if yes then may be i am not getting it..
> >
> > btw one query :-
> >
> > b) if A[N -1 , K] = 1,
> > b1) then *W[N] doesn't belong to the subset* , continue
> > recursively ( goto step a).
> >
> > why???
>
> --
> 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.
[algogeeks] Re: Maximal possible subsets Algorithm
@atul..
The table is used to record the state of subsets not print them.. (I
am assuming that's what u meant)..Hence keeping that in mind, yes it
captures all subsets... Now once A[N, K] is 1 that means there are
some subsets whose sum will be equal to K. Hence, to find all such
subsets we will backtrack accordingly...
--
A[i,j] -> Whether using first 'i' items a sum of 'j' can be made.. A
value of 0/1 indicates whether its possible or not...
Now there are 2 ways we can make a subset having sum j..
1) Consider that W[i] is part of the subset, then A[ i - 1, j - W[i] ]
should be 1.
// Hence while generating the subsets if A[i -1, j - W[i] ] = A[i,
j] =1 , then W[i] will be part of subset... Point to be noted - the
part of "that subset" which will be generated using the path whose
intermediate nodes are (A[i, j] , A[i-1, j - W[i]])
2) Say 'i'th element doesn't contribute to the subset. Hence for A[i,
j] to be 1, A[i-1, j] should be 1.
// Hence when A[i-1, j] = A[i, j] = 1, then W[i] won't be a part
of the subset... Point to be noted - the part of "that subset" which
will be generated using the path whose intermediate nodes are (A[i,
j] , A[i-1, j])
-
On Jan 7, 11:37 pm, atul anand wrote:
> @Lucifer :
>
> for W[]={1,3,2,1,2} and Wmax=4.
> this array will be formed.
>
> 0
>
> 1
>
> 2
>
> 3
>
> 4
>
> 0
>
> 1
>
> 0
>
> 0
>
> 0
>
> 0
>
> 1
>
> 1
>
> 1
>
> 0
>
> 0
>
> 0
>
> 3
>
> 1
>
> 1
>
> 0
>
> 1
>
> 1
>
> 2
>
> 1
>
> 1
>
> 1
>
> 1
>
> 1
>
> 1
>
> 1
>
> 1
>
> 1
>
> 1
>
> 1
>
> 2
>
> 1
>
> 1
>
> 1
>
> 1
>
> 1
>
> is it printing all subset ?? if yes then may be i am not getting it..
>
> btw one query :-
>
> b) if A[N -1 , K] = 1,
> b1) then *W[N] doesn't belong to the subset* , continue
> recursively ( goto step a).
>
> why???
--
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.
Re: [algogeeks] Re: Maximal possible subsets Algorithm
any comments of the following approach. first sort the weights, find the 'j' such that sum( wts from w1 until wj) < Wmax & sum( wts from W1 until Wj+1) > Wmax also 'k' such that sum(wts from Wk to Wn) < Wmax & sum(wts from Wk-1 to Wn) > Wmax so, a = j ( is the max number of elements in any subset,) that satisfies the condition, similatly b = (n-k+1) is the min number of elements in any subset that satisfies the condition. try solving for the subsets of length j and if it fails, try checking for length (j-1) from these j weights. This reduces runtime, but cannot get the runtime --guessing O( n C n/2) -- 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/-/24Q4dqZVSyoJ. 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.
Re: [algogeeks] Re: Maximal possible subsets Algorithm
@Lucifer :
for W[]={1,3,2,1,2} and Wmax=4.
this array will be formed.
0
1
2
3
4
0
1
0
0
0
0
1
1
1
0
0
0
3
1
1
0
1
1
2
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
is it printing all subset ?? if yes then may be i am not getting it..
btw one query :-
b) if A[N -1 , K] = 1,
b1) then *W[N] doesn't belong to the subset* , continue
recursively ( goto step a).
why???
--
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.
[algogeeks] Re: Maximal possible subsets Algorithm
@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 wrote: > @Lucifer : thats okbut 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 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 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 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 < > > 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 > > yo
Re: [algogeeks] Re: Maximal possible subsets Algorithm
@Lucifer : thats okbut 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 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 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 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 < > 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
[algogeeks] Re: Maximal possible subsets Algorithm
@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 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 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. >
[algogeeks] Re: Maximal possible subsets Algorithm
@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
[algogeeks] Re: Maximal possible subsets Algorithm
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 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.
[algogeeks] Re: Maximal possible subsets Algorithm
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 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.
Re: [algogeeks] Re: Maximal possible subsets Algorithm
@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 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.
Re: [algogeeks] Re: Maximal possible subsets Algorithm
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.
[algogeeks] Re: Maximal possible subsets Algorithm
@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.
Re: [algogeeks] Re: Maximal possible subsets Algorithm
As such there's no significance for Vi, it's just to show that objects are
not identical. We don't need to maximize on V. For the sake of problem you
can ignore it. We can use the sum of values for other purpose.
Take an examole: S= {1, 2, 3, 4, 5} are weights (I am not using Values)
. Wmax = 8
Solution:
{1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {3, 5}
On Mon, Dec 5, 2011 at 2:38 PM, sourabh wrote:
> @ Piyush..
>
> I have a doubt... Is there any significance of the value Vi, if yes
> then can u give an example.
> If not, then is your question about finding all maximum subsets where
> the addition of the weights results in maximum (each weight being
> considered only once)...
> Say for ex-
> The max weight is X<=Wmax , then find all subsets which add up to X..
>
>
> On Dec 5, 1:51 pm, Piyush Grover wrote:
> > Yeah but there's one more condition where it says if subset x is a
> > solution then all the subsets of x will not be part of the solution.
> > It should make some difference, exponential time solution is an obvious
> one.
> >
> >
> >
> >
> >
> >
> >
> > On Mon, Dec 5, 2011 at 2:16 PM, saurabh singh
> wrote:
> > > The possibility is ruled out by your question itself.There are
> exponential
> > > subsets of a set,so finding all subset is not possible in polynomail
> time.
> >
> > > A backtracking approach is what you should think on,
> >
> > > On Mon, Dec 5, 2011 at 12:51 PM, Piyush Grover <
> piyush4u.iit...@gmail.com>wrote:
> >
> > >> Given a set S of objects having weights Wi and values Vi, and given a
> > >> maximum weight Wmax.
> > >> Find *ALL* the maximal subsets of set S such that Sum(Wi) <= Wmax.
> >
> > >> Maximal subset means if {a, b, c} is a solution (such that Wa+Wb+Wc
> <=
> > >> Wmax) it means there doesn't exist any other object x in S such that
> > >> Wa+Wb+Wc+Wx <= Wmax and all the subsets of {a, b, c} e.g. {a, b}, {b,
> c},
> > >> {a, c}{c} are not the part of the solution set.
> >
> > >> P.S. Note that I am *not asking the knapsack problem* where we need to
> > >> find the optimal set.
> > >> I am asking *ALL* the possible maximal subsets and looking for a good
> > >> algo (polynomial if exists).
> >
> > >> Thanks
> >
> > >> Piyush
> >
> > >> --
> > >> 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.
> >
> > > --
> > > Saurabh Singh
> > > B.Tech (Computer Science)
> > > MNNIT ALLAHABAD
> >
> > > --
> > > 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.
[algogeeks] Re: Maximal possible subsets Algorithm
@ Piyush..
I have a doubt... Is there any significance of the value Vi, if yes
then can u give an example.
If not, then is your question about finding all maximum subsets where
the addition of the weights results in maximum (each weight being
considered only once)...
Say for ex-
The max weight is X<=Wmax , then find all subsets which add up to X..
On Dec 5, 1:51 pm, Piyush Grover wrote:
> Yeah but there's one more condition where it says if subset x is a
> solution then all the subsets of x will not be part of the solution.
> It should make some difference, exponential time solution is an obvious one.
>
>
>
>
>
>
>
> On Mon, Dec 5, 2011 at 2:16 PM, saurabh singh wrote:
> > The possibility is ruled out by your question itself.There are exponential
> > subsets of a set,so finding all subset is not possible in polynomail time.
>
> > A backtracking approach is what you should think on,
>
> > On Mon, Dec 5, 2011 at 12:51 PM, Piyush Grover
> > wrote:
>
> >> Given a set S of objects having weights Wi and values Vi, and given a
> >> maximum weight Wmax.
> >> Find *ALL* the maximal subsets of set S such that Sum(Wi) <= Wmax.
>
> >> Maximal subset means if {a, b, c} is a solution (such that Wa+Wb+Wc <=
> >> Wmax) it means there doesn't exist any other object x in S such that
> >> Wa+Wb+Wc+Wx <= Wmax and all the subsets of {a, b, c} e.g. {a, b}, {b, c},
> >> {a, c}{c} are not the part of the solution set.
>
> >> P.S. Note that I am *not asking the knapsack problem* where we need to
> >> find the optimal set.
> >> I am asking *ALL* the possible maximal subsets and looking for a good
> >> algo (polynomial if exists).
>
> >> Thanks
>
> >> Piyush
>
> >> --
> >> 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.
>
> > --
> > Saurabh Singh
> > B.Tech (Computer Science)
> > MNNIT ALLAHABAD
>
> > --
> > 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.
