Hilfe bei einem Beweis über eine Eigenschaft einer Lösung für ein bestimmtes algorithmisches Problem.

Question

Unten ist ein Problem, das ich zu lösen versuche:

Es gibt $n$ Personen, denen zugewiesen werden soll $k$Gondeln. Der Erste$q_1$Personen werden mit der ersten Gondel fahren. Der Erste$q_2$Personen aus der verbleibenden Menge fahren mit der zweiten Gondel und so weiter. Am Ende dann:$\sum_{i=1}^{k}q_i = n, q_i\geq1$. Nun, wenn zwei verschiedene Leute$i$ und $j$ Verwenden Sie die gleiche Gondel, die Unbekanntheit der gegebenen Gondel wird um erhöht $u_{i,j} \geq 0$. Wir müssen die Verteilung der Personen auf Gondeln so gestalten, dass die Summe der Unbekannten aller Gondeln so gering wie möglich ist.

Es gibt einen Link zum ursprünglichen Problem.

Wir versuchen eine Lösung mit folgender Idee zu finden:

Für ein gegebenes $1 \leq i \leq k$ und $1 \leq j \leq n$, Lassen $dp[i][j]$ eine Lösung des Problems sein, wenn wir nur die erste betrachten $j$ Personen und $i$Gondeln. Dann haben wir die folgende Wiederholungsformel:$$dp[i][j] = max_{k<j}( dp[i-1][k] + \sum_{a = k+1}^{j}\sum_{b = a+1}^{j}u_{a,b} ) $$

Schließlich kommen wir zu meiner Frage:

Wenn wir bezeichnen $A[i][j]$ dann das minimale k zu sein, so dass die obige Identität gilt $A[i][j] \leq A[i][j+1]$

Können Sie mir helfen, diese Behauptung zu beweisen?

Answer 1

Ich stelle mir vor, dass es hilfreich wäre, Algorithmen zur Partitionierung von Graphen nachzuschlagen. Ausarbeiten -

Definieren Sie ein vollständig verbundenes Diagramm $G$ mit Eckpunkten sind Menschen ($n$ insgesamt) und Kantengewichte sind ihre Unbekanntheit, dh Knoten $i$ und $j$ sind durch eine Kante mit Gewicht verbunden $u_{i,j}$. Im Standardproblem der Graphpartitionierung möchten wir die Knoten zuweisen$k$Partitionen, so dass die Summe der Kantengewichte über Partitionen hinweg minimiert wird. Hier möchten Sie dies stattdessen maximieren (minimieren Sie wiederum die Summe der Kantengewichte innerhalb der Partitionen).