一、問題引入

分書問題是指：已知 n 個人對 m 本書的喜好（n≤m），現要將 m 本書分給 n 個人，每個人只能分到 1 本書，每本書也最多只能分給 1 個人，并且還要求每個人都能分到自己喜歡的書。列出所有滿足要求的方案。

本題請你對任意 n 和 m 嘗試列出全部的解。

輸入格式：
輸入第一行給出兩個正整數 n 和 m（n≤m≤8），即分書問題中的人數和書的數量。
隨后 n 行，每行給出 m 個關系矩陣元素。其中第 i 行第 j 個元素為 1 表示第 i 個人喜歡第 j 本書，為 0 則表示不喜歡。

輸出格式：
按升序列出所有滿足要求的方案，格式為 (s1,?,sn)。其中 si表示第 i 個人分到了第 si本書。

注：方案 (a1,?,an)<(b1,?,bn) 是指存在 1≤k≤n，使得 ai=bi對所有 1≤i<k 成立，并且有 ak<bk。

輸入樣例：

4 5
0 1 0 0 1
1 1 0 1 0
1 0 1 1 0
0 0 0 1 1

輸出樣例：

(2, 1, 3, 4)
(2, 1, 3, 5)
(2, 1, 4, 5)
(2, 4, 1, 5)
(2, 4, 3, 5)
(5, 1, 3, 4)
(5, 2, 1, 4)
(5, 2, 3, 4)

二、解題步驟

1.問題分析思維導圖

2.解題步驟

1. 問題理解：
   ? 有n個人和m本書，n≤m
   ? 每人只能分到一本自己喜歡的書
   ? 每本書只能分配給一個人
   ? 需要找出所有滿足條件的分配方案
2. 算法選擇：
   ? 使用回溯算法遞歸枚舉所有可能的分配方案
   ? 通過剪枝（只考慮喜歡的書和未被分配的書）減少不必要的搜索
3. 實現步驟：
   ? 回溯函數：
   1.終止條件：當所有人都分配了書時，保存當前方案
   2.對于當前人，遍歷所有書：
   ■ 如果書未被分配且當前人喜歡這本書：
   ■ 標記書為已分配
   ■ 遞歸處理下一個人
   ■ 回溯：取消書的分配狀態
   ? 主函數：
   1.讀取輸入：n, m和喜好矩陣
   2.調用回溯函數獲取所有方案
   3.對結果排序并輸出

三、代碼實現

1.代碼

def solve_book_assignment(n, m, preference):def backtrack(person, assigned_books, current_assignment, results):if person == n:# 找到一個完整的分配方案results.append(tuple(current_assignment))returnfor book in range(m):if not assigned_books[book] and preference[person][book]:# 如果書未被分配且當前人喜歡這本書assigned_books[book] = Truecurrent_assignment[person] = book + 1  # 書的編號從 1 開始backtrack(person + 1, assigned_books, current_assignment, results)assigned_books[book] = False  # 回溯results = []assigned_books = [False] * m  # 記錄書是否被分配current_assignment = [0] * n  # 記錄當前分配方案backtrack(0, assigned_books, current_assignment, results)return resultsdef main():n, m = map(int, input().split())preference = []for _ in range(n):row = list(map(int, input().split()))preference.append(row)# 獲取所有分配方案results = solve_book_assignment(n, m, preference)# 按升序輸出for res in sorted(results):print(f"({', '.join(map(str, res))})")if __name__ == "__main__":main()

2.復雜度分析

時間復雜度：O(m!/(m-n)!)
■ 最壞情況下需要枚舉所有排列，即從m本書中選n本的排列數
空間復雜度：O(n+m)

四、個人總結

通過本次實驗，我深入理解了回溯算法在解決組合優化問題中的應用。實驗以分書問題為載體，讓我親身體驗了如何將實際問題轉化為遞歸搜索模型。在實現過程中，我學會了如何設計遞歸函數的終止條件和回溯邏輯，特別是掌握了通過標記數組來避免重復選擇的關鍵技巧。當遇到輸出結果順序不符合要求的情況時，我通過分析比較規則，理解了字典序的本質，最終采用預排序方案解決了輸出順序問題。

調試過程中出現的重復分配錯誤讓我意識到狀態恢復的重要性，這加深了我對回溯算法中"嘗試-撤銷"這一核心思想的理解。通過分析算法復雜度，我認識到雖然回溯法能保證找到所有解，但其時間代價隨問題規模呈階乘級增長，這讓我更加重視剪枝優化的重要性。實驗數據也驗證了理論分析，當n和m接近8時，運行時間明顯增加。

這次實踐不僅讓我掌握了回溯算法的實現細節，更重要的是培養了我將抽象算法轉化為具體代碼的能力。我體會到良好的數據結構設計對算法效率的影響，比如使用布爾數組而非列表來記錄分配狀態可以提升訪問效率。