Thursday, December 28, 2006

Guess Who Gave This Answer In A Newsgroup?

Try to guess who gave this answer. Here is a small hint, the person looks like Anton Szandor LaVey

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


Answer: 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, [name here] 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.


So who gave this answer?

3 comments:

Hugo Kornelis said...

Heh, that question is just too easy! (Acutallly, after just seeing the title of your post, I already suspected who you're refering to).

And his answer is incomplete as well. I have once posted a solution to the knapsack problem in a newsgroup that used a combination of set-based and looping techniques to get a near-optimal solution in a near-optimal performance.

I have planned to write about this on my blog, but I am way to pressed for time at the moment so it will have to wait. If you need the answer now, you'll have to use Google groups to search the usenet archives... ;->

SQL said...

Hugo, mr 'fields are not columns' himself of course (of course you knew that)

btw..... gelukkig nieuw jaar

Hugo Kornelis said...

Danke schön für die gute Wünsche!

Et pour vous aussi un tres bien noel année!