Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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)}.$

Why Brute Force Is Too Expensive

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.

Bitmask DP State

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.

Transition Formula

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.

Why the Recurrence Is Correct

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.

Worked Example: The \(5\times5\) Sample

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.

Connection with Graph Theory

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.

How the Code Works

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').

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=345
2. Assignment problem: Wikipedia — Assignment problem
3. Bitmask / profile dynamic programming: cp-algorithms — Dynamic Programming on Broken Profile / Mask States
4. Matching in graph theory: Wikipedia — Matching (graph theory)
5. Hungarian algorithm: Wikipedia — Hungarian algorithm