Ich habe ein Problem, dass auf der Oberfläche wie 0-1 Rucksack aussieht. Ich habe eine Reihe von möglichen "Kandidaten", die ausgewählt werden können (oder nicht), jeder Kandidat hat ein "Gewicht" (Kosten) und einen potenziellen "Wert". Wäre dies das gesamte Problem, würde ich einen DP-Ansatz verwenden und damit fertig sein. Aber hier ist der Curveball: Es gibt "Partitionierungsbeschränkungen" für die möglichen Kandidaten, die in der endgültigen Lösung sein können.
Was ich meine ist, dass der Kandidatenraum in diskrete Äquivalenzklassen aufgeteilt wird. Für mein spezielles Problem gibt es etwa 300 Kandidaten und 12 mögliche Äquivalenzklassen. Es gibt "Geschäftsregeln", die besagen, dass ich nur bis zu 3 Kandidaten aus den Klassen C1 und 6 von C2, usw. haben kann.
Diese Einschränkung legt nahe, dass ein Graph-Suchtyp-Ansatz Branch-and-Bound-Techniken oder eine andere Form des Beschneidens verwendet, allerdings bin ich etwas ratlos, da ich nur mit der DP-Lösung zu 0-1 Knapsack vertraut bin . Welche Techniken / Ansätze könnten für dieses Problem geeignet sein? Ich habe mir auch überlegt, vielleicht eine Constraint-Programmierbibliothek zu verwenden, bin mir aber nicht sicher, ob es in der Lage wäre, eine Lösung zu finden?
Sie könnten einen Integer Linear Programming-Solver ausprobieren, bei dem es eine binäre Variable für die Auswahl jedes Kandidaten gibt. Die Beschränkungen werden leicht als lineare Ungleichungen ausgedrückt. Mit 300 Variablen sollte ein Löser nicht viel Mühe haben, es zu lösen.
Der einfachste Weg wäre wahrscheinlich, Ihr Problem in einem Textformat wie dem CPLEX LP-Format und verwenden Sie dann einen Solver wie Coin CBC oder GLPK.
Tags und Links algorithm optimization dynamic-programming knapsack-problem