Das kniffelige Teilsummenproblem mit T-SQL gelöst

In diesem Blogbeitrag soll es um eine sehr interessante Herausforderung gehen, auf die ich im Rahmen der Ausbildung unserer Werkstudenten traf und die ich so bisher mit den Standard-T-SQL-Mitteln nicht gelöst bekommen hätte. Das faszinierende Element an der Aufgabe ist die Einfachheit der Fragestellung bei extrem übersichtlicher Datenmenge sowie der einfache Aufbau der Testdaten. Konnte es wirklich sein, dass mich eine simple Tabelle mit nur zwei Spalten und nur 12 Datensätzen derart ins Schwitzen bringt, wo ich doch auf über 15 Jahren Erfahrungen mit dem SQL Server von Microsoft zurückblicken kann und fast täglich damit programmiere?

Für meinen Konferenz-Vortrag „richtig harte Kopfnüsse mit T-SQL.“ habe ich überlegt, wo mir dieses theoretische Konstrukt, welches in der Mathematik und Informatik als „Teilsummenproblem“ bekannt ist, schon mal im Alltag über den Weg gelaufen ist. Abseits des Lehrbuchsbeispiel eines Bankräubers, der nur auf eine begrenze Rucksackkapazität zum Abtransport der Beute zugreifen kann und nun entscheiden muss, welche Säcke er einpackt und welche er aus Platz- und Gewichtsgründen zurücklassen muss, fiel mir eine Anfrage meines kleinen Sohnes ein. Mit Colin hatten wir in jungen Jahren folgende Vereinbarung bei dem Besuch eines Kirmesplatzes getroffen:

  • Colin muss kein eigenes Taschengeld investieren, er bekommt genauso wie seine größere Schwester eine individuelle Summe von Oma, Opa und den Eltern zur Verfügung gestellt
  • Vorab darf er sich im Internet informieren, welche Fahrgeschäfte der Rummel bietet und welche Möglichkeiten der Verköstigung er gerne aufsuchen möchte.
  • Nach Freigabe der jeweiligen Attraktion darf er eine Liste anfertigen, wie er die zur Verfügung stehende Summe ausgeben möchte. Dabei gibt es keine Einschränkungen, theoretisch könnte er alles in Eis oder Geisterbahnfahrten investieren, er kann aber die Attraktionen auch beliebig kombinieren
  • Colin ist von dem Typ Kinder, die gerne am nächsten Schultag bei allen Themen mitreden. Daher versucht er so viele verschiedene Attraktionen wie möglich zu nutzen
  • Seine Sparsamkeit führt dazu, dass er
    • … keinesfalls das gesetzte Limit überschreiten wird, damit er kein eigenes Taschengeld opfern muss
    • … den zur Verfügung gestellten Betrag so weit wie nur eben möglich ausreizt, damit kein Geld verschwendet wird, denn

ungenutzte Beträge verfallen und gehen zurück an Oma, Opa und die Eltern!

Colin war mit dieser kleinen und vermutlich so simplen Matheaufgabe tagelang in seinem Zimmer verschwunden und optimierte mit Papier und Bleistift vor sich hin. Für einen Grundschüler war seine Rechenleistung enorm. Schon für diese extra Lerneinheit ist das Verfahren zu empfehlen 😉 Irgendwann kam er in Begleitung seiner großem Schwester Neela in mein Zimmer und forderte mich auf, das Problem für die Zukunft mit Rechnerunterstützung zu lösen – schließlich sei ich ja Imformatiker. Also warf ich den SQL Server an und schaffte erstmal die Grundvoraussetzungen: Eine entsprechende Tabelle mit Testdaten.

— Schema OKTOBERFEST anlegen, um Objekte sauber der Aufgabe zuordnen zu können

CREATE SCHEMA [Oktoberfest]

GO

— Tabelle ATTRAKTION im Schema OKTOBERFEST anlegen

CREATE TABLE [Oktoberfest].[Attraktion](

         [ID]              [INT] PRIMARY KEY IDENTITY(1,1)

       , [Attraktion]      [NVARCHAR](20)                   NULL

       , [Preis]           [MONEY]                          NULL

) ON [PRIMARY]

GO

— Tabelle ATTRAKTION im Schema OKTOBERFEST mit den Inhalten (beispielhafte Testdaten) aus der Fragestellung füllen

INSERT INTO [Oktoberfest].[Attraktion] VALUES

    (‚Kettenkarussell‚,          2.15)

  , (‚Geisterbahn‚,              4.50)

  , (‚Raupe‚,                    2.80)

  , (‚Würstchenstand‚,           4.20)

  , (‚Softgetränk‚,              1.75)

  , (‚Riesenrad‚,                 5.30)

  , (‚Autoscooter‚,               3.10)

  , (‚Entenangeln‚,              2.40)

  , (‚Dosenwerfen‚,               2.05)

  , (‚Losbude‚,                  1.55)

  , (‚Wilde Maus‚,               4.30)

  , (‚Kamelrennen‚,              1.60)

Doch wie sollte man nun die gewünschten Informationen extrahieren? Trotz des simplen Aufbaus und der geringen Zahl der Testdaten schlug die gewaltige Komplexitätskeule der Kombinatorik gnadenlos zu. Betrachtet man die Fragestellung mit etwas Mathematik, entspricht die Herausforderung nach etwas Vereinfachung (bspw. der Anpassung des Einzelpreises je Attraktion auf einen Durchschnitt) des berühmten „Urnenmodells mit Zurücklegen“.

/*

Wir nennen die Zahl der Kugeln (=Attraktionen) „n“ und die Anzahl der Ziehungen (Fahrten/Einkäufe)

„k“. Die Reihenfolge, in der die Kugeln gezogen werden, ist irrelevant.

Es gilt die mathematische Formel aus der Kombinatorik:

                          n + k – 1

Anzahl Möglichkeiten =  (           )

                            n – 1

_________________________________________________________________________________________________________________

Bei einem Durchschnittspreis von bspw. 3 Euro pro Attraktion und eine Budget von 21 Euro kann man 7 Einkäufe

tätigen. Werden, wie im Beispiel, 12 Attraktionen angeboten ergibt dies:

                           12 + 7 – 1            18               18!              18! 

Anzahl Möglichkeiten =  (              )   =   (    )   =   ————–   =  ——– 

                             12 – 1              11         (18-11)! * 11!      7! * 11!       

                                     6.402.373.705.728.000      6.402.373.705.728.000

                                 =  ———————-  =  ———————  ~  31.835

                                      5.040 * 39.916.800            201.180.672.000

_________________________________________________________________________________________________________________

Bei einem Durchschnittspreis 2,50 Euro, einer Auswahl aus 20 Attraktionen und einem Budget von 30 Euro erreicht 

die Anzahl der Kombinationen schon Höhen, die die TempDB vor ersthafte Probleme stellen kann:

                          20 + 12 – 1           31               31!              31! 

Anzahl Möglichkeiten =  (             )   =   (    )   =   ————–   =  ——– 

                            20 – 1              19         (31-19)! * 19!      12! * 19!       

                                              8.22283865418E+33                  8.22283865418E+33

                                 =  ————————————-  =  ———————  ~  141.120.525

                                     479.001.600 * 121.645.100.408.832.000     5,826819772799118e+23

*/

Damit war relativ schnell klar, dass manuell erstellte Schleifen und Cursor hier nicht zielführend zu nutzen sein werden. Derartige Ideen lassen sich einfach nicht effizient umsetzen und bedeuten dann in der Laufzeitbetrachtung die rote Karte. Aber der SQL Server kennt ja noch ein paar mehr Wege. Ich kam mit einer rekursiven CTE relativ schnell zum Ziel. Diese ist einfach zu verstehen und zu warten, schon durch Microsoft laufzeitoptimiert und einfach aufzurufen. Um das ganze praktisch zu gestalten habe ich die CTE in eine Stored Procedure ausgelagert:

— Prozedur SPASSGELDAUSGEBEN im Schema OKTOBERFEST anlegen

CREATE OR ALTER PROCEDURE [Oktoberfest].[SpassgeldAusgeben]

         @ZielPreis                     MONEY

       , @ProzentualeAbweichung   INTEGER

AS

BEGIN

       SET NOCOUNT ON;

;WITH loopquery

(

         [Letzte_id]

       , [Kosten]

       , [AnzahlAttraktionen]

       , [Attraktionen]

)

AS (

       — Initialisierung der Rekursion

       SELECT

               [att].[ID]                                         AS [ID]

             , [att].[Preis]                                      AS [Preis]

             , 1                                                  AS [AnzahlAttraktionen]

             , CAST([att].[Attraktion] AS VARCHAR(MAX))            AS [Attraktionen]

       FROM [Oktoberfest].[Attraktion]                             AS [att]

      

       UNION ALL

      

       — Rekursion mit der Summierung der Attraktionsanzahl und des Preises

       SELECT

               [p].ID

             , [lq].[Kosten] + [p].[Preis]

             , [AnzahlAttraktionen] + 1

             , CAST([lq].[Attraktionen] + ‚, ‚ + [p].[Attraktion] AS VARCHAR(MAX))

       FROM loopquery                                             AS [lq]

       INNER JOIN [Oktoberfest].[Attraktion] AS [p] ON [p].[ID] >= [lq].[Letzte_id]

       WHERE 1 = 1

             — Abbruchbedingung der Rekursion

             AND [lq].[Kosten] + [p].[Preis] <= @ZielPreis

       )

       — Ausgabe des Ergebnisses

       SELECT –TOP 1 WITH TIES

               @ZielPreis                                                                          AS [Zielpreis]

             , [Kosten]

             , [AnzahlAttraktionen]

             , [Attraktionen]

       FROM loopquery

       WHERE 1=1

             AND [Kosten] >= ((@ZielPreis / 100) * (100 – @ProzentualeAbweichung))

       ORDER BY [Kosten] DESC, [AnzahlAttraktionen] DESC

       END

GO

— ### Hinweis: ###

— Ein-/Auskommentiertes „TOP 1 WITH TIES“ beeinflusst, wie viele und ob gleichwertige bestplatzierte oder nur genau eine

— bestimmte Anzahl bestplatzierter Lösungen angezeigt werden sollen

Der Aufruf der CTE-Prozedur geht dann schnell von der Hand. Man bestückt die notwendigen Parameter und übergibt der Prozedur damit die Information, wie hoch die zur Verfügung stehende Summe ist und ob diese genau zu treffen ist oder eine Abweichung nach unten toleriert wird. Dieser Schwellwert ist in Prozent anzugeben.

SET STATISTICS XML ON

DECLARE @RC                      INTEGER

DECLARE @ZielPreis               MONEY

DECLARE @ProzentualeAbweichung    INTEGER

SET @ZielPreis                   = 8.05

SET @ProzentualeAbweichung        = 0

EXECUTE @RC = [Oktoberfest].[SpassgeldAusgeben]

   @ZielPreis, @ProzentualeAbweichung

GO

SET STATISTICS XML OFF

GO

Übergibt man der Prozedur mit 21.80 Euro und eine erlaubten Abweichung von 2% andere Parameter, ermittelt der SQL Server schon 16.030 mögliche Kombinationen, die die gestellten Bedingungen erfüllen. Dabei wird das Ergebnis nach Grad der Erreichung der Vorgabesumme sowie nach Anzahl der damit nutzbaren Attraktionen sortiert:

DECLARE @RC                      INTEGER

DECLARE @ZielPreis               MONEY

DECLARE @ProzentualeAbweichung    INTEGER

SET @ZielPreis                   = 21.80

SET @ProzentualeAbweichung        = 2

EXECUTE @RC = [Oktoberfest].[SpassgeldAusgeben]

   @ZielPreis, @ProzentualeAbweichung

GO

Mit diesem Stand nun eine Lösung zu entwickeln, die die Anzahl der unterschiedlichen Attraktionen zählt und danach zu sortieren ist dann nur noch eine Fingerübung…

Teilen:

Share on linkedin
Share on xing
Share on email

Schreiben Sie einen Kommentar