0-1 矩陣每行每列唯一 1 的最大化問題：雙邊匹配 / N 皇後變體

問題建模

給定 M×N 0-1 矩陣，可將 0 翻轉為 1 (或理解為選擇位置放置 1)，要求最終每行、每列**恰好**一個 1，求最大化 1 的總數 (即最大匹配數)。

核心洞察：二分圖最大匹配

• 行集合 U = {r1..rM}，列集合 V = {c1..cN}。
• 原矩陣中 a[i][j]=1 表示邊 (ri, cj) 可用 (或權重為 1)。
• 目標：選擇最大邊集，使任意兩邊不共用端點 → **二分圖最大匹配**。
• 最大匹配數 ≤ min(M, N)。

算法選擇

與 N 皇後關係

N 皇後要求任意兩皇后不同行、不同列、不同對角線。**本問題僅約束行列**，無對角線約束，故是 N 皇後的**子問題/簡化版**，可用二分圖匹配高效求解，而 N 皇後需回溯/位運算。

MATLAB 實現提示

% 構建鄰接矩陣
adj = double(A); % A 為原 0-1 矩陣
% 使用 MATLAB 內置最大匹配 (需工具箱) 或自寫匈牙利
matching = maxBipartiteMatching(adj); % 返回匹配對
maxOnes = length(matching);

結論

本質是**二分圖最大匹配**，而非 N 皇後。用匈牙利或 Hopcroft-Karp 算法可在多項式時間內求得最大 1 的個數及具體位置。