Fabian Rohlik
← all Quizzes
Für das Vertex Cover Problem auf einem Baum $T$ ist die DP-Rekurrenz $M[i] = \min(A[i], B[i])$, wobei $A[i]$ die Cover-Größe einschließlich Knoten $i$ und $B[i]$ ohne Knoten $i$ ist. Was ist $B[i]$?
Ein Array ist 'summy', wenn jedes Element $a_i$ (außer dem ersten) die Summe einer Teilmenge der vorhergehenden Elemente ist. Der DP-Zustand $DP[i][k]$ prüft, ob die Summe $k$ mit einer Teilmenge der ersten $i$ Elemente gebildet werden kann.
Für das Problem 'Gibt es zwei disjunkte Teilmengen $I_1, I_2$ mit $\sum_{i \in I_1} a_i = \sum_{j \in I_2} a_j$?' kann man mit DP prüfen, ob zwei verschiedene Teilmengen denselben Wert ergeben.
Das 0/1-Knapsack-Problem kann mit dynamischer Programmierung in $O(nW)$ Zeit gelöst werden, wobei $n$ die Anzahl der Objekte und $W$ die Kapazität ist.
Gegeben Array $A$, Zielsumme $C$ und Ziel-Quadratsumme $D$. Bestimmen Sie, ob eine Teilmenge existiert, die beides erfüllt. Was ist der DP-Zustand?