分书问题的递归枚举算法

一、问题引入

分书问题是指：已知 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))
            return
        
        for book in range(m):
            if not assigned_books[book] and preference[person][book]:
                # 如果书未被分配且当前人喜欢这本书
                assigned_books[book] = True
                current_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 results

def 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时，运行时间明显增加。

这次实践不仅让我掌握了回溯算法的实现细节，更重要的是培养了我将抽象算法转化为具体代码的能力。我体会到良好的数据结构设计对算法效率的影响，比如使用布尔数组而非列表来记录分配状态可以提升访问效率。