We are given an \(n\times n\) matrix and must choose exactly one entry from each row and exactly one from each column so that the total sum is as large as possible. This is the maximum-weight assignment problem, or equivalently a maximum-weight perfect matching in a complete bipartite graph.
Let \(A=(A_{r,c})_{0\le r,c\lt n}\) be the matrix. Any valid selection is completely determined by a permutation \(\pi\in S_n\): row \(r\) is matched with column \(\pi(r)\). Therefore the target quantity is
$$\max_{\pi\in S_n}\sum_{r=0}^{n-1} A_{r,\pi(r)}.$$
A direct search would test all \(n!\) permutations. For \(n=15\), this means
$$15! = 1{,}307{,}674{,}368{,}000,$$
which is far too large for exhaustive enumeration. The only practical route is to reuse overlapping subproblems, which is exactly what dynamic programming does.
The key observation is that after assigning the first \(r\) rows, the only information that matters is which columns have already been used. We encode this set by a bitmask \(\text{mask}\in[0,2^n)\), where bit \(c\) is 1 iff column \(c\) has been taken.
Define
$$dp[\text{mask}] = \text{best sum after assigning the first } \operatorname{popcount}(\text{mask}) \text{ rows.}$$
If \(r=\operatorname{popcount}(\text{mask})\), then rows \(0,1,\dots,r-1\) have already been assigned, and row \(r\) is the next row to process. The base case is the empty assignment:
$$dp[0]=0.$$
There is no loss of generality in fixing the row order in advance. Every valid assignment still appears exactly once; only the chosen columns vary.
From a reachable state \(\text{mask}\), let \(r=\operatorname{popcount}(\text{mask})\). For every unused column \(c\), we may assign row \(r\) to column \(c\). In code, the next mask is obtained by setting bit \(c\):
$$dp[\text{next}] = \max\bigl(dp[\text{next}],\,dp[\text{mask}] + A_{r,c}\bigr),\qquad \text{next}=\text{mask}\mid(1\ll c).$$
When \(\text{mask}=(1\ll n)-1\), all columns have been used exactly once, so this full-mask state stores the optimum value.
Every feasible assignment defines a unique path through mask states: start from the empty mask, then after processing row 0 one column is marked, after row 1 another column is marked, and so on until the full mask is reached. Conversely, every such path chooses one distinct column per row and therefore corresponds to a valid assignment.
Because the objective is additive, once the used-column set is fixed, the only relevant quantity is the best sum already achieved for that mask. Taking the maximum over all predecessors guarantees that \(dp[\text{mask}]\) is optimal for that partial state, so the full mask yields the global optimum.
The C++ solution includes the \(5\times5\) sample matrix from the problem statement as a checkpoint. In that case the DP explores masks from \(0\) to \(2^5-1=31\), and each mask represents one partial matching between the first few rows and distinct columns.
The optimal value for that sample is
$$3315,$$
which matches the known sample result. This checkpoint verifies that both the state definition and the transition formula are implemented correctly before solving the full \(15\times15\) instance.
If rows are viewed as left-side vertices and columns as right-side vertices, then each entry \(A_{r,c}\) is the weight of edge \((r,c)\). The problem becomes a maximum-weight perfect matching problem in a bipartite graph. The Hungarian algorithm also solves this class of problems in polynomial time, but for \(n=15\) the bitmask DP is simpler and still comfortably fast.
The C++, Java, and Python solutions all use the same structure. They allocate a one-dimensional array dp of size \(2^n\), initialize all states to an unreachable sentinel value except dp[0]=0, and iterate over masks in increasing order.
For each reachable mask, the current row is obtained from the population count of the mask, and every unused column is tested. If assigning that column improves the destination state, the DP value is updated. In C++ this uses __builtin_popcount, in Java Integer.bitCount, and in Python bin(mask).count('1').
There are exactly \(2^n\) masks. Each mask tries up to \(n\) columns, so the running time is
$$O(n2^n).$$
The DP table stores one value per mask, so the memory usage is
$$O(2^n).$$
For \(n=15\), this means \(2^{15}=32768\) states, which is small enough to compute the exact optimum very comfortably.
Gegeben ist eine \(n\times n\)-Matrix. Es soll genau ein Eintrag aus jeder Zeile und genau ein Eintrag aus jeder Spalte gewählt werden, sodass die Gesamtsumme maximal wird. Das ist das Zuordnungsproblem mit maximalem Gewicht, äquivalent zu einem perfekten Matching maximalen Gewichts in einem vollständigen bipartiten Graphen.
Sei \(A=(A_{r,c})_{0\le r,c\lt n}\) die Matrix. Jede zulässige Auswahl wird vollständig durch eine Permutation \(\pi\in S_n\) beschrieben: Zeile \(r\) wird Spalte \(\pi(r)\) zugeordnet. Gesucht ist also
$$\max_{\pi\in S_n}\sum_{r=0}^{n-1} A_{r,\pi(r)}.$$
Eine naive Suche müsste alle \(n!\) Permutationen prüfen. Für \(n=15\) ist das
$$15! = 1{,}307{,}674{,}368{,}000,$$
also viel zu groß für vollständiges Durchprobieren. Man muss überlappende Teilprobleme wiederverwenden, und genau das leistet dynamische Programmierung.
Die zentrale Beobachtung ist: Nachdem die ersten \(r\) Zeilen zugeordnet wurden, ist nur noch relevant, welche Spalten bereits benutzt sind. Diese Menge wird durch eine Bitmaske \(\text{mask}\in[0,2^n)\) kodiert; Bit \(c\) ist genau dann 1, wenn Spalte \(c\) schon belegt ist.
Definiere
$$dp[\text{mask}] = \text{beste Summe nach Zuordnung der ersten } \operatorname{popcount}(\text{mask}) \text{ Zeilen.}$$
Ist \(r=\operatorname{popcount}(\text{mask})\), dann sind die Zeilen \(0,1,\dots,r-1\) bereits vergeben, und Zeile \(r\) ist die nächste zu bearbeitende Zeile. Der Startzustand ist die leere Zuordnung:
$$dp[0]=0.$$
Dass die Zeilen in fester Reihenfolge verarbeitet werden, ist keine Einschränkung. Jede zulässige Gesamtzuordnung erscheint trotzdem genau einmal; nur die Spaltenwahl variiert.
Für einen erreichbaren Zustand \(\text{mask}\) sei \(r=\operatorname{popcount}(\text{mask})\). Für jede noch freie Spalte \(c\) darf Zeile \(r\) auf Spalte \(c\) gelegt werden. Im Code erhält man die Folgemaske, indem man Bit \(c\) setzt:
$$dp[\text{next}] = \max\bigl(dp[\text{next}],\,dp[\text{mask}] + A_{r,c}\bigr),\qquad \text{next}=\text{mask}\mid(1\ll c).$$
Wenn \(\text{mask}=(1\ll n)-1\) ist, wurde jede Spalte genau einmal verwendet; dieser Vollmaskenzustand enthält also das Optimum.
Jede zulässige Zuordnung erzeugt genau einen Weg durch die Maskenzustände: Man startet bei der leeren Maske, markiert nach Zeile 0 eine Spalte, nach Zeile 1 eine weitere und so weiter bis zur Vollmaske. Umgekehrt beschreibt jeder solche Weg eine gültige Auswahl von genau einer verschiedenen Spalte pro Zeile.
Da die Zielfunktion additiv ist, genügt es für einen festen Zustand zu wissen, welche Spalten schon benutzt wurden und welche beste Summe dort bisher erreicht wurde. Das Maximum über alle Vorgängerzustände stellt sicher, dass \(dp[\text{mask}]\) den besten partiellen Wert enthält; deshalb liefert die Vollmaske das globale Optimum.
Die C++-Lösung enthält die \(5\times5\)-Beispielmatrix aus der Aufgabenstellung als Checkpoint. In diesem Fall durchläuft die DP alle Masken von \(0\) bis \(2^5-1=31\), wobei jede Maske ein partielles Matching zwischen den ersten Zeilen und verschiedenen Spalten repräsentiert.
Der optimale Wert für dieses Beispiel ist
$$3315,$$
und stimmt damit mit dem bekannten Beispielergebnis überein. So wird die Implementierung überprüft, bevor die vollständige \(15\times15\)-Matrix gelöst wird.
Interpretiert man die Zeilen als linke Knoten und die Spalten als rechte Knoten, dann trägt jede Matrixzelle \(A_{r,c}\) das Gewicht der Kante \((r,c)\). Die Aufgabe wird damit zu einem perfekten Matching maximalen Gewichts in einem bipartiten Graphen. Auch der ungarische Algorithmus löst dieses Problem in Polynomialzeit; für \(n=15\) ist die Bitmasken-DP jedoch einfacher und zugleich schnell genug.
Die C++-, Java- und Python-Lösungen verwenden dieselbe Struktur. Es wird ein eindimensionales Array dp der Länge \(2^n\) angelegt, alle Zustände werden zunächst auf einen unerreichbaren Sentinelwert gesetzt, nur dp[0]=0 nicht. Danach werden die Masken in aufsteigender Reihenfolge verarbeitet.
Für jede erreichbare Maske bestimmt der Code die aktuelle Zeile über die Anzahl gesetzter Bits und testet dann jede noch freie Spalte. Verbessert die Wahl dieser Spalte den Zielzustand, wird der DP-Wert aktualisiert. In C++ geschieht die Bitanzahl mit __builtin_popcount, in Java mit Integer.bitCount und in Python mit bin(mask).count('1').
Es gibt genau \(2^n\) Masken. Pro Maske werden bis zu \(n\) Spalten ausprobiert, daher beträgt die Laufzeit
$$O(n2^n).$$
Die DP-Tabelle speichert einen Wert pro Maske, also liegt der Speicherverbrauch bei
$$O(2^n).$$
Für \(n=15\) bedeutet das \(2^{15}=32768\) Zustände; damit lässt sich das exakte Optimum sehr komfortabel berechnen.
Elimizde \(n\times n\) boyutunda bir matris var. Her satırdan tam bir eleman ve her sütundan tam bir eleman seçilecek şekilde toplamın en büyüklenmesi isteniyor. Bu, maksimum ağırlıklı assignment problemi, yani eşdeğer olarak tam iki parçalı bir graf üzerinde maksimum ağırlıklı perfect matching problemidir.
\(A=(A_{r,c})_{0\le r,c\lt n}\) matrisi verilsin. Geçerli her seçim bir permütasyon \(\pi\in S_n\) ile tamamen belirlenir: satır \(r\), sütun \(\pi(r)\) ile eşleştirilir. Dolayısıyla hedefimiz
$$\max_{\pi\in S_n}\sum_{r=0}^{n-1} A_{r,\pi(r)}.$$
Doğrudan arama yapmak tüm \(n!\) permütasyonları denemeyi gerektirir. \(n=15\) için bu sayı
$$15! = 1{,}307{,}674{,}368{,}000,$$
olur. Bu büyüklükte bir uzayda tam tarama pratik değildir. Bu yüzden örtüşen alt problemleri yeniden kullanmak gerekir; dinamik programlama tam olarak bunu sağlar.
Temel gözlem şudur: İlk \(r\) satır atandıktan sonra geriye kalan kararlar açısından önemli olan tek bilgi hangi sütunların kullanıldığıdır. Bu kümeyi \(\text{mask}\in[0,2^n)\) bitmask'i ile kodlarız; \(c\). bit 1 ise sütun \(c\) daha önce seçilmiştir.
Tanım:
$$dp[\text{mask}] = \text{ilk } \operatorname{popcount}(\text{mask}) \text{ satır atandığında elde edilebilen en iyi toplam.}$$
Eğer \(r=\operatorname{popcount}(\text{mask})\) ise \(0,1,\dots,r-1\) satırları zaten atanmıştır ve sıradaki satır \(r\)'dir. Başlangıç durumu boş atamadır:
$$dp[0]=0.$$
Satırları sabit sırayla işlemek herhangi bir genellik kaybı yaratmaz. Geçerli her tam atama yine tam bir kez temsil edilir; değişen tek şey sütun seçimidir.
Erişilebilir bir \(\text{mask}\) durumu için \(r=\operatorname{popcount}(\text{mask})\) olsun. Kullanılmamış her \(c\) sütunu için satır \(r\) bu sütuna atanabilir. Kodda sonraki durum, \(c\). bitin açılmasıyla elde edilir:
$$dp[\text{next}] = \max\bigl(dp[\text{next}],\,dp[\text{mask}] + A_{r,c}\bigr),\qquad \text{next}=\text{mask}\mid(1\ll c).$$
\(\text{mask}=(1\ll n)-1\) olduğunda tüm sütunlar tam bir kez kullanılmış olur; bu full-mask durumu optimum değeri taşır.
Her geçerli atama maskeler üzerinde tek bir yol üretir: boş maskeden başlanır, satır 0 işlendiğinde bir sütun işaretlenir, satır 1 işlendiğinde bir başka sütun eklenir ve bu süreç full-mask'e kadar sürer. Tersi de doğrudur: boş maskeden full-mask'e giden ve her adımda yeni bir sütun ekleyen her yol, satır başına bir seçim ve sütun başına tek kullanım anlamına gelir.
Amaç fonksiyonu toplamsal olduğu için, belirli bir maskeye ulaşıldığında önemli olan şey o maskede şimdiye kadar elde edilmiş en yüksek toplamdır. Tüm önceki durumlardan gelen adaylar arasında maksimumu almak, \(dp[\text{mask}]\)'in o alt problem için en iyi değeri tutmasını garanti eder. Dolayısıyla full-mask global optimumu verir.
C++ çözümü, problem metnindeki \(5\times5\) örnek matrisi bir checkpoint olarak içerir. Bu durumda DP, \(0\) ile \(2^5-1=31\) arasındaki tüm maskeleri dolaşır; her maske ilk birkaç satır ile farklı sütunlar arasındaki kısmi bir eşlemeyi temsil eder.
Bu örnek için optimum değer
$$3315,$$
olup bilinen örnek sonucu ile aynıdır. Böylece tam \(15\times15\) matris çözülmeden önce hem durum tanımı hem de geçiş formülü doğrulanmış olur.
Satırları sol taraftaki düğümler, sütunları sağ taraftaki düğümler olarak düşünürsek, her \(A_{r,c}\) matrisi hücresi \((r,c)\) kenarının ağırlığına dönüşür. Böylece problem, iki parçalı bir graf üzerinde maksimum ağırlıklı perfect matching bulma problemine eşdeğer olur. Hungarian algoritması da bu sınıfı polinom zamanda çözer; ancak \(n=15\) için bitmask DP hem daha sade hem de fazlasıyla hızlıdır.
C++, Java ve Python çözümleri aynı iskeleti kullanır. Uzunluğu \(2^n\) olan tek boyutlu bir dp dizisi ayrılır; bütün durumlar erişilemez bir sentinel değerle başlatılır, yalnızca dp[0]=0 bırakılır. Ardından maskeler artan sırayla işlenir.
Her erişilebilir maske için mevcut satır, maskenin bit sayısından elde edilir ve kullanılmamış her sütun denenir. Eğer bu seçim hedef durumu iyileştiriyorsa DP değeri güncellenir. C++ sürümünde bunun için __builtin_popcount, Java'da Integer.bitCount, Python'da ise bin(mask).count('1') kullanılır.
Toplam \(2^n\) adet maske vardır. Her maske için en fazla \(n\) sütun denenir; dolayısıyla zaman karmaşıklığı
$$O(n2^n).$$
DP tablosu her maske için bir değer tuttuğundan bellek karmaşıklığı da
$$O(2^n).$$
\(n=15\) için bu, \(2^{15}=32768\) durum demektir. Bu boyut, tam optimumun rahatlıkla hesaplanmasına imkan verir.
Se nos da una matriz \(n\times n\) y debemos elegir exactamente una entrada de cada fila y exactamente una de cada columna, de modo que la suma total sea máxima. Este es el problema de asignación de peso máximo, o de forma equivalente, un emparejamiento perfecto de peso máximo en un grafo bipartito completo.
Sea \(A=(A_{r,c})_{0\le r,c\lt n}\) la matriz. Toda selección válida queda determinada por una permutación \(\pi\in S_n\): la fila \(r\) se empareja con la columna \(\pi(r)\). Por tanto, el objetivo es
$$\max_{\pi\in S_n}\sum_{r=0}^{n-1} A_{r,\pi(r)}.$$
Una búsqueda directa tendría que probar las \(n!\) permutaciones posibles. Para \(n=15\), eso significa
$$15! = 1{,}307{,}674{,}368{,}000,$$
una cantidad demasiado grande para enumerarla por completo. Necesitamos reutilizar subproblemas superpuestos, y justamente eso es lo que hace la programación dinámica.
La observación clave es que, tras asignar las primeras \(r\) filas, lo único que importa es qué columnas ya han sido usadas. Codificamos ese conjunto con una máscara \(\text{mask}\in[0,2^n)\), donde el bit \(c\) vale 1 si la columna \(c\) ya está ocupada.
Definimos
$$dp[\text{mask}] = \text{la mejor suma tras asignar las primeras } \operatorname{popcount}(\text{mask}) \text{ filas.}$$
Si \(r=\operatorname{popcount}(\text{mask})\), entonces las filas \(0,1,\dots,r-1\) ya están resueltas y la fila \(r\) es la siguiente en procesarse. El caso base es la asignación vacía:
$$dp[0]=0.$$
Fijar de antemano el orden de las filas no pierde generalidad. Toda asignación válida sigue apareciendo exactamente una vez; lo único que cambia es qué columnas se escogen.
Desde un estado alcanzable \(\text{mask}\), sea \(r=\operatorname{popcount}(\text{mask})\). Para cada columna libre \(c\), podemos asignar la fila \(r\) a esa columna. En el código, la siguiente máscara se obtiene activando el bit \(c\):
$$dp[\text{next}] = \max\bigl(dp[\text{next}],\,dp[\text{mask}] + A_{r,c}\bigr),\qquad \text{next}=\text{mask}\mid(1\ll c).$$
Cuando \(\text{mask}=(1\ll n)-1\), todas las columnas ya han sido usadas exactamente una vez, así que esa máscara completa contiene el valor óptimo.
Toda asignación factible define un camino único por los estados de máscara: se empieza en la máscara vacía, después de la fila 0 se marca una columna, después de la fila 1 se añade otra, y así sucesivamente hasta llegar a la máscara completa. A la inversa, todo camino de este tipo elige una columna nueva en cada paso y por tanto representa una asignación válida.
Como la función objetivo es aditiva, una vez fijado el conjunto de columnas ya usadas, solo importa la mejor suma parcial alcanzada para esa máscara. Tomar el máximo sobre todos los predecesores garantiza que \(dp[\text{mask}]\) sea óptimo para ese subproblema, y en consecuencia la máscara completa da el óptimo global.
La solución en C++ incluye la matriz de muestra \(5\times5\) del enunciado como checkpoint. En ese caso, la DP recorre todas las máscaras desde \(0\) hasta \(2^5-1=31\), y cada máscara representa un emparejamiento parcial entre las primeras filas y columnas distintas.
El valor óptimo para esa muestra es
$$3315,$$
que coincide con la respuesta conocida del ejemplo. Este checkpoint confirma que tanto el estado como la transición están implementados correctamente antes de resolver la instancia completa de \(15\times15\).
Si interpretamos las filas como vértices del lado izquierdo y las columnas como vértices del lado derecho, cada entrada \(A_{r,c}\) pasa a ser el peso de la arista \((r,c)\). Así, el problema se convierte en hallar un emparejamiento perfecto de peso máximo en un grafo bipartito. El algoritmo húngaro también resuelve este tipo de problemas en tiempo polinómico, pero para \(n=15\) la DP con bitmask es más simple y sigue siendo sobradamente rápida.
Las versiones en C++, Java y Python siguen la misma estructura. Reservan un arreglo unidimensional dp de tamaño \(2^n\), inicializan todos los estados con un valor centinela de inalcanzable salvo dp[0]=0, y recorren las máscaras en orden creciente.
Para cada máscara alcanzable, el código obtiene la fila actual mediante el número de bits activos y luego prueba cada columna libre. Si esa elección mejora el estado destino, actualiza el valor de la DP. En C++ se usa __builtin_popcount, en Java Integer.bitCount y en Python bin(mask).count('1').
Hay exactamente \(2^n\) máscaras. Cada una prueba hasta \(n\) columnas, así que el tiempo total es
$$O(n2^n).$$
La tabla DP guarda un valor por máscara, de modo que la memoria es
$$O(2^n).$$
Para \(n=15\), esto significa \(2^{15}=32768\) estados, una cantidad lo bastante pequeña como para calcular el óptimo exacto con comodidad.
给定一个 \(n\times n\) 矩阵，需要从每一行恰好选一个元素、从每一列也恰好选一个元素，并使总和最大。这就是最大权指派问题；等价地，也可以看成完全二分图上的最大权完美匹配问题。
设矩阵为 \(A=(A_{r,c})_{0\le r,c\lt n}\)。任意一个合法选择都可由一个排列 \(\pi\in S_n\) 唯一描述：第 \(r\) 行对应第 \(\pi(r)\) 列。因此目标可以写成
$$\max_{\pi\in S_n}\sum_{r=0}^{n-1} A_{r,\pi(r)}.$$
如果直接搜索，就要枚举全部 \(n!\) 个排列。对 \(n=15\) 而言，这个数量是
$$15! = 1{,}307{,}674{,}368{,}000,$$
显然过于庞大，无法直接穷举。必须复用大量重复子问题，而这正是动态规划的优势所在。
关键观察是：当前若已经给前 \(r\) 行做完分配，那么接下来真正重要的信息只有“哪些列已经被使用”。我们用一个位掩码 \(\text{mask}\in[0,2^n)\) 表示这个集合；如果第 \(c\) 位为 1，就表示列 \(c\) 已被占用。
定义
$$dp[\text{mask}] = \text{给前 } \operatorname{popcount}(\text{mask}) \text{ 行完成分配后所能得到的最大和。}$$
若 \(r=\operatorname{popcount}(\text{mask})\)，则第 \(0,1,\dots,r-1\) 行已经处理完，第 \(r\) 行是下一行。初始状态为空分配：
$$dp[0]=0.$$
把行固定按顺序处理不会丢失一般性。每个合法方案仍然会被表示一次，只是列的选择在变化。
对于一个可达状态 \(\text{mask}\)，令 \(r=\operatorname{popcount}(\text{mask})\)。对每个尚未使用的列 \(c\)，都可以把第 \(r\) 行分配给它。代码里，下一个状态就是把第 \(c\) 位设为 1：
$$dp[\text{next}] = \max\bigl(dp[\text{next}],\,dp[\text{mask}] + A_{r,c}\bigr),\qquad \text{next}=\text{mask}\mid(1\ll c).$$
当 \(\text{mask}=(1\ll n)-1\) 时，说明所有列都恰好使用了一次，因此这个满掩码状态保存的就是最优值。
每个合法指派都会对应一条唯一的掩码路径：从空掩码出发，处理完第 0 行后标记一列，处理完第 1 行后再加入一列，如此继续直到满掩码。反过来，任何一条每步都新增一列的路径，也恰好定义了“每行选一列、每列只选一次”的合法方案。
由于目标函数是可加的，所以一旦已用列集合固定下来，真正需要保留的信息只有该状态下目前能达到的最大部分和。对所有前驱取最大值，就能保证 \(dp[\text{mask}]\) 是该子问题的最优解，因此满掩码自然给出全局最优解。
C++ 解法中包含题目给出的 \(5\times5\) 样例矩阵作为检查点。此时 DP 会遍历从 \(0\) 到 \(2^5-1=31\) 的全部掩码，每个掩码都表示前若干行与若干不同列之间的一种部分匹配。
该样例的最优值为
$$3315,$$
与题目样例答案一致。这个检查点可以在求解完整 \(15\times15\) 矩阵之前先验证状态定义与转移公式都正确无误。
如果把行看作左侧顶点、列看作右侧顶点，那么矩阵元素 \(A_{r,c}\) 就是边 \((r,c)\) 的权值。这样原问题就转化为二分图上的最大权完美匹配问题。匈牙利算法也能在多项式时间内解决这一类问题，但在 \(n=15\) 这种规模下，位掩码 DP 更直接，实现也更简单。
C++、Java 和 Python 版本的结构完全一致。它们分配一个长度为 \(2^n\) 的一维数组 dp，除 dp[0]=0 外，其余状态全部初始化为“不可达”的哨兵值，然后按掩码从小到大遍历。
对于每个可达掩码，代码先通过掩码中 1 的个数得到当前行，再枚举所有未使用的列。如果这次选择能改进目标状态，就更新 DP 值。C++ 使用 __builtin_popcount，Java 使用 Integer.bitCount，Python 使用 bin(mask).count('1')。
状态总数恰好是 \(2^n\)。每个状态最多尝试 \(n\) 个列，因此时间复杂度为
$$O(n2^n).$$
DP 表为每个掩码存一个值，所以空间复杂度为
$$O(2^n).$$
当 \(n=15\) 时，\(2^{15}=32768\) 个状态规模很小，因此可以非常轻松地求出精确最优解。
Дана квадратная матрица \(n\times n\). Нужно выбрать ровно по одному элементу из каждой строки и из каждого столбца так, чтобы суммарное значение было максимальным. Это задача о назначениях максимального веса, эквивалентная задаче о совершенном паросочетании максимального веса в полном двудольном графе.
Пусть \(A=(A_{r,c})_{0\le r,c\lt n}\) — данная матрица. Любой допустимый выбор полностью задаётся перестановкой \(\pi\in S_n\): строка \(r\) сопоставляется столбцу \(\pi(r)\). Следовательно, нужно максимизировать
$$\max_{\pi\in S_n}\sum_{r=0}^{n-1} A_{r,\pi(r)}.$$
Прямой перебор означал бы проверку всех \(n!\) перестановок. Для \(n=15\) это
$$15! = 1{,}307{,}674{,}368{,}000,$$
что слишком велико для полного перебора. Значит, нужно переиспользовать пересекающиеся подзадачи, а это как раз и делает динамическое программирование.
Ключевое наблюдение такое: после назначения первых \(r\) строк важно только то, какие столбцы уже заняты. Это множество кодируется битовой маской \(\text{mask}\in[0,2^n)\); бит \(c\) равен 1 тогда и только тогда, когда столбец \(c\) уже использован.
Определим
$$dp[\text{mask}] = \text{лучшая сумма после назначения первых } \operatorname{popcount}(\text{mask}) \text{ строк.}$$
Если \(r=\operatorname{popcount}(\text{mask})\), то строки \(0,1,\dots,r-1\) уже обработаны, а строка \(r\) идёт следующей. Базовый случай — пустое назначение:
$$dp[0]=0.$$
Фиксированный порядок строк не ограничивает общность. Каждое допустимое полное назначение всё равно рассматривается ровно один раз; меняется только выбор столбцов.
Пусть \(\text{mask}\) — достижимое состояние, а \(r=\operatorname{popcount}(\text{mask})\). Для каждого свободного столбца \(c\) можно назначить строку \(r\) на столбец \(c\). В коде следующая маска получается установкой бита \(c\):
$$dp[\text{next}] = \max\bigl(dp[\text{next}],\,dp[\text{mask}] + A_{r,c}\bigr),\qquad \text{next}=\text{mask}\mid(1\ll c).$$
Когда \(\text{mask}=(1\ll n)-1\), все столбцы использованы ровно по одному разу, значит полная маска хранит оптимальное значение.
Каждому допустимому назначению соответствует единственный путь по маскам: начинаем с пустой маски, после обработки строки 0 отмечаем один столбец, после строки 1 — ещё один и так далее до полной маски. Обратно, любой путь, который на каждом шаге добавляет ровно один новый столбец, задаёт корректный выбор по одному столбцу на строку и без повторов.
Так как целевая функция аддитивна, после фиксации множества уже занятых столбцов важно лишь лучшее частичное значение для этой маски. Взятие максимума по всем предшественникам гарантирует, что \(dp[\text{mask}]\) содержит оптимум для данной подзадачи, а значит полная маска даёт глобальный оптимум.
В C++-решении присутствует матрица-пример \(5\times5\) из условия как checkpoint. В этом случае DP перебирает все маски от \(0\) до \(2^5-1=31\), и каждая маска представляет некоторое частичное паросочетание между первыми строками и различными столбцами.
Оптимальное значение для этого примера равно
$$3315,$$
что совпадает с известным ответом из условия. Такой checkpoint подтверждает корректность и состояния, и перехода до запуска на полной матрице \(15\times15\).
Если считать строки левыми вершинами, а столбцы правыми, то каждый элемент \(A_{r,c}\) становится весом ребра \((r,c)\). Тогда задача превращается в поиск совершенного паросочетания максимального веса в двудольном графе. Её также решает венгерский алгоритм за полиномиальное время, но для \(n=15\) DP по битмаскам проще и при этом более чем достаточно быстро работает.
Реализации на C++, Java и Python устроены одинаково. Они создают одномерный массив dp длины \(2^n\), заполняют все состояния значением «недостижимо», кроме dp[0]=0, после чего проходят маски по возрастанию.
Для каждой достижимой маски текущая строка вычисляется по числу установленных битов, затем перебираются все ещё свободные столбцы. Если такой выбор улучшает целевое состояние, значение DP обновляется. В C++ используется __builtin_popcount, в Java — Integer.bitCount, в Python — bin(mask).count('1').
Всего имеется \(2^n\) масок. Для каждой маски проверяется до \(n\) столбцов, поэтому временная сложность равна
$$O(n2^n).$$
Таблица DP хранит одно значение на маску, следовательно, память составляет
$$O(2^n).$$
Для \(n=15\) это \(2^{15}=32768\) состояний, так что точный оптимум вычисляется совершенно комфортно.
لدينا مصفوفة \(n\times n\)، ونريد اختيار عنصر واحد بالضبط من كل صف وعنصر واحد بالضبط من كل عمود بحيث يكون المجموع الكلي أكبر ما يمكن. هذه هي مسألة الإسناد ذات الوزن الأعظمي، وهي مكافئة أيضًا لمسألة إيجاد مطابقة كاملة ذات وزن أعظمي في رسم بياني ثنائي كامل.
لتكن \(A=(A_{r,c})_{0\le r,c\lt n}\) هي المصفوفة. كل اختيار صحيح يحدَّد بالكامل بواسطة تبديل \(\pi\in S_n\): الصف \(r\) يُسند إلى العمود \(\pi(r)\). لذلك تصبح الكمية المطلوبة
$$\max_{\pi\in S_n}\sum_{r=0}^{n-1} A_{r,\pi(r)}.$$
الحل المباشر يتطلب فحص جميع التبديلات وعددها \(n!\). عندما \(n=15\) يصبح العدد
$$15! = 1{,}307{,}674{,}368{,}000,$$
وهو عدد هائل لا يمكن تعدادُه عمليًا. لذلك نحتاج إلى إعادة استخدام المسائل الجزئية المتداخلة، وهذا بالضبط ما تفعله البرمجة الديناميكية.
الفكرة الأساسية هي أنه بعد إسناد أول \(r\) صفوف، فإن المعلومة الوحيدة المهمة لما تبقى هي: ما الأعمدة التي استُخدمت بالفعل؟ نمثل هذه المجموعة بقناع بتات \(\text{mask}\in[0,2^n)\)، بحيث يكون البت \(c\) مساويًا لـ 1 إذا كان العمود \(c\) مستخدمًا.
نعرّف
$$dp[\text{mask}] = \text{أفضل مجموع ممكن بعد إسناد أول } \operatorname{popcount}(\text{mask}) \text{ صفوف.}$$
إذا كان \(r=\operatorname{popcount}(\text{mask})\)، فهذا يعني أن الصفوف \(0,1,\dots,r-1\) أُسنِدت بالفعل، وأن الصف \(r\) هو الصف التالي. حالة البداية هي الإسناد الفارغ:
$$dp[0]=0.$$
تثبيت ترتيب الصفوف مسبقًا لا يفقد أي عمومية؛ فكل إسناد صحيح كامل سيظهر مرة واحدة تمامًا، والمتغير الوحيد هو اختيار الأعمدة.
لنفترض أن \(\text{mask}\) حالة قابلة للوصول، ولْيكن \(r=\operatorname{popcount}(\text{mask})\). لكل عمود غير مستخدم \(c\)، يمكن إسناد الصف \(r\) إلى هذا العمود. في الكود، الحالة التالية تُبنى بتفعيل البت \(c\):
$$dp[\text{next}] = \max\bigl(dp[\text{next}],\,dp[\text{mask}] + A_{r,c}\bigr),\qquad \text{next}=\text{mask}\mid(1\ll c).$$
وعندما يصبح \(\text{mask}=(1\ll n)-1\)، تكون جميع الأعمدة قد استُخدمت مرة واحدة بالضبط، وبالتالي فإن حالة القناع الكامل تحتوي القيمة المثلى.
كل إسناد صالح يحدّد مسارًا وحيدًا عبر حالات الأقنعة: نبدأ من القناع الفارغ، وبعد معالجة الصف 0 نعلّم عمودًا واحدًا، وبعد الصف 1 نضيف عمودًا آخر، وهكذا حتى نصل إلى القناع الكامل. وبالعكس، فإن أي مسار يضيف عمودًا جديدًا في كل خطوة يعبّر عن اختيار صحيح: عمود واحد لكل صف، ومن دون تكرار للأعمدة.
ولأن دالة الهدف تجميعية، فإنه بعد تثبيت مجموعة الأعمدة المستخدمة، لا يبقى مهمًا إلا أفضل مجموع جزئي تحقق لهذا القناع. أخذ القيمة العظمى على جميع الحالات السابقة يضمن أن \(dp[\text{mask}]\) هو الحل الأمثل لذلك الجزء من المسألة، ومن ثم يعطي القناع الكامل الحل الأمثل العام.
يتضمن حل ++C المصفوفة النموذجية \(5\times5\) الموجودة في نص المسألة على شكل checkpoint. في هذه الحالة تستكشف البرمجة الديناميكية جميع الأقنعة من \(0\) حتى \(2^5-1=31\)، ويمثل كل قناع مطابقة جزئية بين الصفوف الأولى وأعمدة مختلفة.
القيمة المثلى لهذه العينة هي
$$3315,$$
وهي مطابقة تمامًا للإجابة المعروفة في المثال. وهذا يسمح بالتحقق من صحة تعريف الحالة وصيغة الانتقال قبل تشغيل الحل على مصفوفة \(15\times15\) الكاملة.
إذا اعتبرنا الصفوف عقدًا في الجهة اليسرى، والأعمدة عقدًا في الجهة اليمنى، فإن كل عنصر \(A_{r,c}\) يصبح وزن الحافة \((r,c)\). عندها تتحول المسألة إلى إيجاد مطابقة كاملة ذات وزن أعظمي في رسم بياني ثنائي. كما أن خوارزمية هنغارية تحل هذه الفئة من المسائل بزمن كثير حدود، لكن عند \(n=15\) تكون برمجة الأقنعة أبسط في التنفيذ وسريعة جدًا في الوقت نفسه.
حلول ++C وJava وPython تتبع البنية نفسها. فهي تنشئ مصفوفة أحادية البعد dp بطول \(2^n\)، وتملأ جميع الحالات بقيمة حارسة تعني "غير قابل للوصول" باستثناء dp[0]=0، ثم تمر على الأقنعة بترتيب تصاعدي.
لكل قناع قابل للوصول، يحدد الكود الصف الحالي عبر عدد البتات المفعلة، ثم يجرّب كل عمود غير مستخدم. إذا حسّن هذا الاختيار الحالة الهدف، يُحدَّث مقدار DP. في ++C يُستخدم __builtin_popcount، وفي Java يُستخدم Integer.bitCount، وفي Python يُستخدم bin(mask).count('1').
يوجد بالضبط \(2^n\) من الأقنعة. ولكل قناع يمكن تجربة حتى \(n\) أعمدة، لذا فإن التعقيد الزمني هو
$$O(n2^n).$$
أما جدول DP فيخزن قيمة واحدة لكل قناع، ومن ثم يكون التعقيد المكاني
$$O(2^n).$$
عندما \(n=15\)، فهذا يعني \(2^{15}=32768\) حالة فقط، وهو حجم صغير بما يكفي لحساب الحل الأمثل الدقيق بسهولة.