Posted by --CELKO-- on 12/01/06 14:43

>> I guess the key question for me is, can this be done entirely in SQL? <<

The answer is always "Yes, we can do it in SQL!"

The right answer is "But, like a size 26 thong, just because you can
does not mean you should!"

Google around for "Bin packing" and/or "Knapsack" problems on some math
websites. This is a known NP-complete problem. In English, it means
that the only way to solve it is to try all possible combinations, so
the execution time grows fastrer than any polynominal expression (i.e
think about factorials or worse).

There are often several valid solutions, too. Being a set-oriented
language, SQL will attempt to find the set of ALL solutions. And run
forever.

This is a job for a procedure (yes, Celko is saying nice thing about
procedural code!) which will stop at the first usable answer, even if
it is not optimal. Now you have to pick your algorithm. This is
usually the Greedy algorithm ("grab the biggest bite you can and add it
to the answer; see if you met the goal; if not, repeat") modified to do
some back tracking.

[Back to original message]