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 <saurab...@gmail.com> 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.
