Rucksackproblem in MSSQL

SchlumpinatorSQL

Neuer Benutzer
Beiträge
2
Hallo liebes Datenbankforum!

Seit ein paar Wochen beschäftige ich mich mit Datenbanken, Darstellung und Abfragen. Nun habe ich ein Problem, bei dem ich nicht wirklich weiterkomme. Deshalb würde ich mich über eure Hilfe sehr freuen!

Es geht darum, dass in einer Tabelle in einer MSSQL Datenbank folgende Sachen stehen:

Name (als vchar), Marktwert (als int), Punkte (als int)

Die Tabelle hat ungefähr 150 Datensätze.

Nun möchte ich eine lineare Optimierung der Punkte unter der Nebenbedingung eines maximalen Budgets durchführen. In der Uni kann ich das mit der Simplex Methode auf Blatt und Papier auch lösen. Hier fällt es mir aber viel schwerer.
Konkret möchte ich also eine Liste der Datensätze erhalten, die aufsummiert die meisten Punkte haben, einen gesamten Marktwert aber nicht überschreiten.

Dazu habe ich jetzt viel gelesen und bin auf das Rucksackproblem aufmerksam geworden. Jedoch schaffe ich es einfach nicht, das auf meine Tabelle anzuwenden. Für jede Hilfe bin ich sehr dankbar!
 
Werbung:
Leider kann ich den Beitrag oben nicht mehr bearbeiten.

Das hier ist mein Ansatz bislang:

Code:
SELECT *
INTO #KnapsackItems
FROM [Kickbase_Datenbank].[dbo].[OLE DB Gesamtpunkte];

WITH UNIQUEnTuples (n, Tuples, ID, [Marktwert], [Gesamtpunkte]) AS (
    SELECT 1, CAST(Spieler AS nvarchar(4000)), Spieler, [Marktwert], [Gesamtpunkte]
    FROM #KnapsackItems
    UNION ALL
    SELECT 1 + n.n, t.Spieler + ',' + n.Tuples, Spieler, n.[Marktwert] + t.[Marktwert], n.Gesamtpunkte + t.Gesamtpunkte
    FROM UNIQUEnTuples n
    CROSS APPLY (
        SELECT Spieler, [Marktwert], Gesamtpunkte
        FROM #KnapsackItems t
        WHERE t.Spieler < n.ID AND n.[Marktwert] + t.[Marktwert] < 400) t
    )
SELECT TOP 5 *
FROM UNIQUEnTuples
ORDER BY Gesamtpunkte DESC, n, Tuples;

GO
DROP TABLE #KnapsackItems;
 
Werbung:
Leider habe ich nur wirklich Realschul-Mathe abgeschlossen und so verlockend es klingt mich nie mit dem "Rucksackproblem" oder "lineare Optimierung" befasst.

Du nutzt Rekursion in deinem Ansatz, das klingt erstmal nicht ganz abwegig. Liefert dein Ansatz den brauchbare Werte?
 
Zurück
Oben