Welche Art von Algorithmus ist das?

Question

Welche Art von Algorithmus ist das, ich weiß so ziemlich nichts, aber das ist, was ich im Code zu tun versuche ... Ich habe Klasse 'Element', Eigenschaften int A und int B - Ich habe mehrere Listen von List<Item> mit einem zufällige Menge von Item in jeder Liste, incisentent mit jeder anderen Liste. Ich muss 1 Punkt aus jeder Liste wählen, um den höchstmöglichen Wert der Summe Item.A zu erhalten, während ich gleichzeitig festlege, dass die Summe Item.B auch mindestens eine bestimmte Zahl sein muss. In Zukunft könnte auch eine andere Eigenschaft Item.C entsprechen, dass die Summe einer bestimmten Zahl entsprechen muss. Ich habe keine Ahnung, wie man schreibt diese :(

So ist es auf diese Weise zu setzen;

class Item 
    int A 
    int B 
    int C 

Ich habe ein 10-fach verschiedene List<Item> jeweils mit einer beliebigen Anzahl von Artikeln innerhalb

Wir müssen finden die genau die beste Kombination

a) Highest sum of Item.A 
b) Constraint that the sum of Item.B must be higher than X 
c) Constraint that the sum of Item.C must be equal to X 

ich habe keine Ahnung zu haben, wie dies zu codieren schnell und effizient zu sein. :(

Answer 1

Wie in meinem Kommentar erwähnt, ist dies ein Binärprogrammierungsproblem, das als multi-dimensional Knapsack problem umgewandelt werden kann. Ich würde zuerst versuchen, es mit einem Standard Mixed Integer Programming (MIP) Solver zu lösen, wie der von Lieven in einem seiner Kommentare vorgeschlagen (lpSolve), vorausgesetzt, dass Sie "nur" einige 100-200 binäre Variablen haben . Sie müssen vielleicht ein wenig mit den Parametern herumspielen. Einige MIP-Solver ermöglichen das Hinzufügen von Suchheuristiken, die hilfreich sein können. Angesichts Ihrer Einschränkungen muss ich zugeben, dass ich kein Gefühl dafür habe, wie lange ein Standard-MIP-Solver dauert, aber ich würde nicht den Atem anhalten.

Wenn ein Mixed-Integer-Programmierlöser nicht schnell genug für Sie ist, sollten Sie sich einige speziellere Algorithmen ansehen. Für Ihr Problem sind die in Knapsack Problems, Kapitel 11.10, zum Multiple-Choice-Knapsack-Problem (fast genau Ihr Problem) und Kapitel 9 dargestellten relevant.

Edit: basierend auf Ihre Kommentare, die gute Nachricht ist, dass Ihre Datenbereiche sind ziemlich gut und das Problem scheint in einer angemessenen Zeit lösbar. Diese paper (DOI für den Fall, dass der Link verschwindet) präsentiert einen Algorithmus, der nach Angaben der Autoren Probleme Ihrer Größe innerhalb von Sekunden löst (siehe Abschnitt 4.4 und 5.1). Die schlechte Nachricht ist, dass es viel Mathematik enthält ...

Answer 2

Ich stellte diese Frage als nicht registrierter Benutzer und Register klicken, dauerte es nicht meine nicht registrierte Benutzer mit meinem registrierten Benutzer, schön =/

In Bezug auf den Kommentar von van assoziieren:

Typischerweise gibt wird etwa 14 Listen oder so sein. Innerhalb jeder Liste wird es in der Regel rund 5-15 'Artikel' Jeder Artikel hat diese 3 Eigenschaften. Wir müssen genau 1 Artikel aus jeder Liste. Wir suchen den maximalen Wert von PropertyA, wenn wir die Summe aller PropertyA berechnen, nachdem wir einen Eintrag aus jeder Liste ausgewählt haben. Die Constraints sind PropertyB und PropertyC, die die gewählte Kombination ebenfalls bestätigen muss, wiederum unter Verwendung der Summe der Werte über die Kombination.

Es muss auch die optimale Lösung sein, keine Näherung.