C 語言回溯法求解 5 人 5 書分配問題：滿足偏好矩陣的完整分配方案

問題建模

• 5 人：A,B,C,D,E（索引 0~4）。
• 5 書：0,1,2,3,4。
• 偏好矩陣 Like[5][5]，1 表示喜歡。
• 目標：找到排列 assign[5]，使 Like[i][assign[i]] == 1 且所有書不重複。

回溯算法

bool dfs(int person) {
    if (person == 5) return true; // 全部分配完成
    for (int book = 0; book < 5; ++book) {
        if (!used[book] && Like[person][book]) {
            used[book] = true;
            assign[person] = book;
            if (dfs(person + 1)) return true;
            used[book] = false; // 回溯
        }
    }
    return false;
}

唯一解

A -> 2
B -> 0
C -> 1
D -> 3
E -> 4

驗證：每人獲得喜歡的書，書籍無衝突。

擴展

• 輸出所有可行解：移除 return true，收集方案。
• 引入權重求最優：最大化總滿意度（匈牙利算法 / KM 算法）。