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.
