|
|
Posted by Ed Murphy on 12/02/06 05:05
--CELKO-- wrote:
> 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.
As I understood it, the original poster already had such an algorithm
in mind: "sort the images in random order, then try grabbing them one
at a time, until you've failed five times". (Or fallen off the end of
the list.)
Navigation:
[Reply to this message]
|