【C++】分书问题：深入解析、回溯法高级应用与理论拓展

---

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

---

---

---

💯前言

• 分书问题是回溯法在组合优化与约束满足问题中的一个典型应用。尽管问题规模较小，但背后反映出的搜索空间生成、约束条件裁剪与方案排序等问题，恰恰是算法设计中值得深思的核心内容。本篇文章将面向有较高编程基础的读者，深入解析题目本质，提供详细的代码实现与理论优化，同时对回溯法的应用进行拓展探讨，展示其在算法研究与工程实践中的广泛适用性。此外，我们还会对回溯法的特点、复杂度分析和其在更复杂问题中的推广进行深入讨论，帮助读者系统掌握这一经典算法的应用与演变。
  C++ 参考手册
  

---

💯题目描述

问题背景
设有 $N$ 本书与 $N$ 个人，每个人对书籍的喜好用一个二维矩阵 $like[i][j]$ 表示：

• 若 $like[i][j]=1$，表示第 $i$ 个人喜欢第 $j$ 本书；
• 若 $like[i][j]=0$，表示第 $i$ 个人不喜欢第 $j$ 本书。

问题目标
设计一个程序，输出所有满足以下条件的分书方案：

1. 每本书分配给一个人，且每个人最多得到一本书；
2. 分配方案中，所有人都必须喜欢自己分到的书。

输入格式：

• 第 $1$ 行：整数 $N$（$1\le N\le 5$）；
• 接下来的 $N$ 行：矩阵 $like$，每行包含 $N$ 个整数 $0$ 或 $1$。

输出格式：

• 每行输出一种合法的分书方案。
• 输出按字典序排序，方案格式为：第 $1\sim N$ 本书依次分配给的人的编号。

输入示例：

5
0 1 1 0 0
1 1 0 0 1
0 1 1 0 1
0 0 0 1 0
0 1 0 0 1

输出示例：

2 3 1 4 5
2 5 1 4 3

---

💯思路与算法

本题实质是一个排列组合搜索问题，涉及约束条件过滤，所有的可行方案需按照字典序输出。因此，解题的核心在于：

1. 搜索空间构建：所有书的分配方案。
2. 约束条件：分配给某人的书，必须是他喜欢的书。
3. 去重与排序：利用回溯法，按字典序遍历所有合法方案。

---

回溯法理论基础

回溯法是深度优先搜索（DFS）的一种形式，适用于组合问题、排列问题以及约束满足问题。其基本过程包括：

1. 状态选择：逐步选择合法的解分配到当前状态。
2. 约束剪枝：对于不满足条件的状态，及时停止搜索。
3. 回溯撤销：当搜索结束或无解时，撤销当前状态，回到上一步尝试其他选择。

本题中，书本与人存在一一映射关系，状态空间的规模为 $N!$（阶乘）。借助回溯法，可以对 $N!$ 的状态进行搜索，同时通过约束 $like[i][j]$ 进行剪枝，大幅缩小搜索空间。此外，回溯的每一步都需要确保：当前分配的状态合法，且不会影响后续的决策。

---

💯代码实现与解析

---

完整代码

#include <bits/stdc++.h>
using namespace std;int N;
int like[6][6];        // 1-based 矩阵，表示喜好关系
bool used[6];          // 标记某人是否已分配书
int assign[6];         // 每本书的分配结果
vector<vector<int>> solutions;  // 存储所有合法方案// 回溯函数
void backtrack(int book) {if (book > N) {  // 所有书已分配solutions.emplace_back(assign + 1, assign + N + 1);return;}for (int person = 1; person <= N; person++) {if (!used[person] && like[person][book]) {  // 当前人喜欢这本书且未分配used[person] = true;assign[book] = person;backtrack(book + 1);used[person] = false;  // 撤销选择，回溯}}
}int main() {cin >> N;for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) {cin >> like[i][j];}}backtrack(1);  // 从第一本书开始分配sort(solutions.begin(), solutions.end());  // 对所有方案按字典序排序for (const auto &sol : solutions) {for (int i = 0; i < N; i++) {cout << sol[i] << (i == N - 1 ? '\n' : ' ');}}return 0;
}

---

代码关键步骤解析

1. 搜索空间的遍历：通过回溯法逐步尝试所有可能的分配方案。
2. 约束过滤：利用 like 矩阵剪枝，排除不合法的分配。
3. 状态回溯：递归结束后，恢复当前状态，继续尝试其他方案。
4. 结果排序：所有方案按字典序输出，满足题目要求。

---

💯时间复杂度与空间复杂度分析

• 搜索空间规模：$N!$（最大 120）。
• 剪枝操作：有效减少无效分配，优化搜索效率。
• 排序复杂度：$O(M\log M)$，其中 $M$ 是合法方案的数量。

整体时间复杂度为：
$$O(N!+M\log M)$$
空间复杂度为：$O(N)$，用于存储当前状态和递归栈。

---

💯理论拓展：回溯法的高级应用

回溯法在约束满足问题（CSP）中扮演核心角色，例如：

1. N 皇后问题：将 N 个皇后放置在 $N\times N$ 棋盘上，确保任意两个皇后不互相攻击。
2. 数独求解：填充数独表格，满足所有行、列和子区域的约束。
3. 图的着色问题：为图的顶点分配颜色，确保相邻顶点颜色不同。

在实际应用中，回溯法还可以结合启发式搜索与动态约束传播，进一步提升求解效率。

---

💯小结

• 
  分书问题通过回溯法求解，展现了搜索空间构建、约束剪枝与方案排序的有机结合。本篇文章不仅详细解析了问题的解决思路与代码实现，还拓展讨论了回溯法在 CSP 问题中的应用与复杂度分析。通过掌握回溯法这一基础算法，读者可以在更多复杂问题中找到高效而系统的解决方案，进一步推动算法设计与实践的深入探索。

---

---