# Knapsacks and Numbers

This article provides the SQL that does this, and also a PL/SQL package containing a pipelined function that applies a slightly different algorithm; the latter is also practical, although it proved less efficient on my test problems.

Problem Definition

• The calculation can be expressed as an additive combination of products
• Within each product, each number occurs once with a power between -P and +P, including zero
• All possible products will be considered
• Each element in the combination has a coefficient between -C and +C, including zero
• The combination has a fixed number of elements, E
• The numbers are entered into a table, and a fixed number of them, N, are to be considered
• The queries are to be generic, parametrised by P, C, E, N, and target value T
• Integer division is messy, so I use real numbers and exclude non-integral complete products so that the order doesn’t matter
• (Added 070813:)Optionally, a number can appear in at most one combination, using the BitAnd idea I borrrowed from Stew’s solution

Test Problems

I used two test problems.

Test Problem 1: Brazilian League
The first …

```
```

Note that …

SQL Solution with Recursive Subquery Factoring

SQL

Note that currently I have retained the fantasy league table and column names, but they could as well be the generic items and categories in place of players and teams: This is a generic solution.

How It Works

The solution approach is based on the method used to provide exact solutions for knapsack problems in my earlier article, but with a number of extensions to cater for the new category constraints, and to reduce searching to manageable proportions.

Results

Test Problem 1: Brazilian League

The pipelined function solved this in 5 seconds, while the SQL solution solved it in 21 seconds. The solutions were identical, as follows:

```
```

Conclusions

My idea for using recursive subquery factoring to solve combinatorial optimisation problems, such as knapsack problems, described in other articles on my blog, was previously only practical for small problems. The extensions described here render it a practical proposition even for larger problems. It is also relatively simple compared with procedural approaches.

Metallic rose gold hues are sure to mark a member of charge

Colour: Rose Gold

Key
like to take your balloon – along with the service