Re: Looking for an algorithm to accomplish the following

That is what I was afraid of. I was trying to avoid having to do complete
enumeration, but I could not think of any other way. As the number of sets
increase, the performance will definitely decrease.

<C6L1V@xxxxxxx> wrote in message
news:1125449992.747538.120220@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>I believe your problem is NP-complete (or worse), meaning that there
> is, in general, no "nice" algorithm to solve it in the worst case. (For
> example, it may be necessary to perform complete enumeration!) The
> reason I say this is that even if your sets have only TWO attributes
> (such as X and Y) the problem of deciding if there is a subset having
> sum(X) >=a and sum(Y) <=b is NP-complete. I suspect that having four
> attributes will make the problem no easier.
>
> Ray Vickson
> Adjunct Professor, Univ. of Waterloo
>


.