Investoren und Pools - Rückzieher

Question

Ich habe beschlossen, das Konzept der Rückzieher zu lernen, tiefer und ich habe folgende Aufgabe:

Da N Investoren, M Städte, N durch M-Matrix P Anlegerpräferenzen (P [i, j ] = 1, wenn der i-te Investor möchte, dass der Pool in der j-ten Stadt gebaut wird, P [i, j] = 0 dann ist er neutral und wenn P [i, j] = -1 ist er skeptisch) und Akzeptanzniveau L (wenn die Summe der Anlegerpräferenzen bei einer bestimmten Standortwahl größer oder gleich L ist, halten wir ihn für überzeugt). Finden Sie eine maximale Anzahl von Investoren, die überzeugt werden können und Städte in welchen Pools gebaut werden sollen.

Ich habe versucht, Backtracking zu verwenden, aber ich frage mich, ob es möglich ist, es mehr zu optimieren. Vorerst, auf jeder Rekursionsebene, halte ich fest, wie viele Menschen möglicherweise überzeugt werden können. Wenn diese Zahl kleiner oder gleich meinem aktuellen Maximum ist, dann kehre ich zurück (es gibt keine bessere Antwort).

Answer 1

Ich bin mir nicht sicher, ob das das ist, wonach Sie suchen, aber mit einem kleinen Trick können Sie das Problem als ein ganzzahliges lineares Programm (ILP) ausdrücken. Dann können Sie einen Ganzzahl-Linear-Programmier-Löser (zum Beispiel GLPK) verwenden, um eine optimale Lösung zu finden.

Let s[i] 0-1 Integer-Variablen sein (i über Investoren bis hin) und c[j] 0-1 Integer-Variablen über die Städte hin und K eine große Zahl sein (L + the number of investors tun wird).

Dann ist Ihr Problem sum(s[i]) so dass für jeden i, sum(P[i, j]*c[j]) + s[i] * K >= L zu minimieren. Der Wert von sum(s[i]) in der optimalen Lösung ist die Anzahl der unzufriedenen Investoren, und c[j] gibt an, ob in der Stadt ein Pool j zu bauen.

Diese Formulierung des Problems ist in einer Standardform für ILPs, also sind Sie gut zu gehen.