---

博客主頁(yè)： [小????????] 本文專欄: C++

---

---

---

💯前言

• 分書問題是回溯法在組合優(yōu)化與約束滿足問題中的一個(gè)典型應(yīng)用。盡管問題規(guī)模較小，但背后反映出的搜索空間生成、約束條件裁剪與方案排序等問題，恰恰是算法設(shè)計(jì)中值得深思的核心內(nèi)容。本篇文章將面向有較高編程基礎(chǔ)的讀者，深入解析題目本質(zhì)，提供詳細(xì)的代碼實(shí)現(xiàn)與理論優(yōu)化，同時(shí)對(duì)回溯法的應(yīng)用進(jìn)行拓展探討，展示其在算法研究與工程實(shí)踐中的廣泛適用性。此外，我們還會(huì)對(duì)回溯法的特點(diǎn)、復(fù)雜度分析和其在更復(fù)雜問題中的推廣進(jìn)行深入討論，幫助讀者系統(tǒng)掌握這一經(jīng)典算法的應(yīng)用與演變。
  C++ 參考手冊(cè)
  

---

💯題目描述

問題背景
設(shè)有 $N$ 本書與 $N$ 個(gè)人，每個(gè)人對(duì)書籍的喜好用一個(gè)二維矩陣 $like[i][j]$ 表示：

• 若 $like[i][j]=1$，表示第 $i$ 個(gè)人喜歡第 $j$ 本書；
• 若 $like[i][j]=0$，表示第 $i$ 個(gè)人不喜歡第 $j$ 本書。

問題目標(biāo)
設(shè)計(jì)一個(gè)程序，輸出所有滿足以下條件的分書方案：

1. 每本書分配給一個(gè)人，且每個(gè)人最多得到一本書；
2. 分配方案中，所有人都必須喜歡自己分到的書。

輸入格式：

• 第 $1$ 行：整數(shù) $N$（$1\le N\le 5$）；
• 接下來的 $N$ 行：矩陣 $like$，每行包含 $N$ 個(gè)整數(shù) $0$ 或 $1$。

輸出格式：

• 每行輸出一種合法的分書方案。
• 輸出按字典序排序，方案格式為：第 $1～N$ 本書依次分配給的人的編號(hào)。

輸入示例：

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

---

💯思路與算法

本題實(shí)質(zhì)是一個(gè)排列組合搜索問題，涉及約束條件過濾，所有的可行方案需按照字典序輸出。因此，解題的核心在于：

1. 搜索空間構(gòu)建：所有書的分配方案。
2. 約束條件：分配給某人的書，必須是他喜歡的書。
3. 去重與排序：利用回溯法，按字典序遍歷所有合法方案。

---

回溯法理論基礎(chǔ)

回溯法是深度優(yōu)先搜索（DFS）的一種形式，適用于組合問題、排列問題以及約束滿足問題。其基本過程包括：

1. 狀態(tài)選擇：逐步選擇合法的解分配到當(dāng)前狀態(tài)。
2. 約束剪枝：對(duì)于不滿足條件的狀態(tài)，及時(shí)停止搜索。
3. 回溯撤銷：當(dāng)搜索結(jié)束或無(wú)解時(shí)，撤銷當(dāng)前狀態(tài)，回到上一步嘗試其他選擇。

本題中，書本與人存在一一映射關(guān)系，狀態(tài)空間的規(guī)模為 $N!$（階乘）。借助回溯法，可以對(duì) $N!$ 的狀態(tài)進(jìn)行搜索，同時(shí)通過約束 $like[i][j]$ 進(jìn)行剪枝，大幅縮小搜索空間。此外，回溯的每一步都需要確保：當(dāng)前分配的狀態(tài)合法，且不會(huì)影響后續(xù)的決策。

---

💯代碼實(shí)現(xiàn)與解析

---

完整代碼

#include <bits/stdc++.h>
using namespace std;int N;
int like[6][6];        // 1-based 矩陣，表示喜好關(guān)系
bool used[6];          // 標(biāo)記某人是否已分配書
int assign[6];         // 每本書的分配結(jié)果
vector<vector<int>> solutions;  // 存儲(chǔ)所有合法方案// 回溯函數(shù)
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]) {  // 當(dāng)前人喜歡這本書且未分配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());  // 對(duì)所有方案按字典序排序for (const auto &sol : solutions) {for (int i = 0; i < N; i++) {cout << sol[i] << (i == N - 1 ? '\n' : ' ');}}return 0;
}

---

代碼關(guān)鍵步驟解析

1. 搜索空間的遍歷：通過回溯法逐步嘗試所有可能的分配方案。
2. 約束過濾：利用 like 矩陣剪枝，排除不合法的分配。
3. 狀態(tài)回溯：遞歸結(jié)束后，恢復(fù)當(dāng)前狀態(tài)，繼續(xù)嘗試其他方案。
4. 結(jié)果排序：所有方案按字典序輸出，滿足題目要求。

---

💯時(shí)間復(fù)雜度與空間復(fù)雜度分析

• 搜索空間規(guī)模：$N!$（最大 120）。
• 剪枝操作：有效減少無(wú)效分配，優(yōu)化搜索效率。
• 排序復(fù)雜度：$O(M\log M)$，其中 $M$ 是合法方案的數(shù)量。

整體時(shí)間復(fù)雜度為：
$$O(N!+M\log M)$$
空間復(fù)雜度為：$O(N)$，用于存儲(chǔ)當(dāng)前狀態(tài)和遞歸棧。

---

💯理論拓展：回溯法的高級(jí)應(yīng)用

回溯法在約束滿足問題（CSP）中扮演核心角色，例如：

1. N 皇后問題：將 N 個(gè)皇后放置在 $N\times N$ 棋盤上，確保任意兩個(gè)皇后不互相攻擊。
2. 數(shù)獨(dú)求解：填充數(shù)獨(dú)表格，滿足所有行、列和子區(qū)域的約束。
3. 圖的著色問題：為圖的頂點(diǎn)分配顏色，確保相鄰頂點(diǎn)顏色不同。

在實(shí)際應(yīng)用中，回溯法還可以結(jié)合啟發(fā)式搜索與動(dòng)態(tài)約束傳播，進(jìn)一步提升求解效率。

---

💯小結(jié)

• 
  分書問題通過回溯法求解，展現(xiàn)了搜索空間構(gòu)建、約束剪枝與方案排序的有機(jī)結(jié)合。本篇文章不僅詳細(xì)解析了問題的解決思路與代碼實(shí)現(xiàn)，還拓展討論了回溯法在 CSP 問題中的應(yīng)用與復(fù)雜度分析。通過掌握回溯法這一基礎(chǔ)算法，讀者可以在更多復(fù)雜問題中找到高效而系統(tǒng)的解決方案，進(jìn)一步推動(dòng)算法設(shè)計(jì)與實(shí)踐的深入探索。

---

---