網(wǎng)站二維碼彈窗推廣優(yōu)化網(wǎng)站排名教程
文章目錄
- 💯前言
- 💯題目描述
- 💯思路與算法
- 回溯法理論基礎(chǔ)
- 💯代碼實(shí)現(xiàn)與解析
- 完整代碼
- 代碼關(guān)鍵步驟解析
- 💯時(shí)間復(fù)雜度與空間復(fù)雜度分析
- 💯理論拓展:回溯法的高級(jí)應(yīng)用
- 💯小結(jié)
💯前言
- 分書問題是回溯法在組合優(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 N 本書與 N N N 個(gè)人,每個(gè)人對(duì)書籍的喜好用一個(gè)二維矩陣 l i k e [ i ] [ j ] like[i][j] like[i][j] 表示:
- 若 l i k e [ i ] [ j ] = 1 like[i][j] = 1 like[i][j]=1,表示第 i i i 個(gè)人喜歡第 j j j 本書;
- 若 l i k e [ i ] [ j ] = 0 like[i][j] = 0 like[i][j]=0,表示第 i i i 個(gè)人不喜歡第 j j j 本書。
問題目標(biāo)
設(shè)計(jì)一個(gè)程序,輸出所有滿足以下條件的分書方案:
- 每本書分配給一個(gè)人,且每個(gè)人最多得到一本書;
- 分配方案中,所有人都必須喜歡自己分到的書。
輸入格式:
- 第 1 1 1 行:整數(shù) N N N( 1 ≤ N ≤ 5 1 \leq N \leq 5 1≤N≤5);
- 接下來的 N N N 行:矩陣 l i k e like like,每行包含 N N N 個(gè)整數(shù) 0 0 0 或 1 1 1。
輸出格式:
- 每行輸出一種合法的分書方案。
- 輸出按字典序排序,方案格式為:第 1 ~ N 1 \sim N 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è)排列組合搜索問題,涉及約束條件過濾,所有的可行方案需按照字典序輸出。因此,解題的核心在于:
- 搜索空間構(gòu)建:所有書的分配方案。
- 約束條件:分配給某人的書,必須是他喜歡的書。
- 去重與排序:利用回溯法,按字典序遍歷所有合法方案。
回溯法理論基礎(chǔ)
回溯法是深度優(yōu)先搜索(DFS)的一種形式,適用于組合問題、排列問題以及約束滿足問題。其基本過程包括:
- 狀態(tài)選擇:逐步選擇合法的解分配到當(dāng)前狀態(tài)。
- 約束剪枝:對(duì)于不滿足條件的狀態(tài),及時(shí)停止搜索。
- 回溯撤銷:當(dāng)搜索結(jié)束或無(wú)解時(shí),撤銷當(dāng)前狀態(tài),回到上一步嘗試其他選擇。
本題中,書本與人存在一一映射關(guān)系,狀態(tài)空間的規(guī)模為 N ! N! N!(階乘)。借助回溯法,可以對(duì) N ! N! N! 的狀態(tài)進(jìn)行搜索,同時(shí)通過約束 l i k e [ i ] [ j ] like[i][j] 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)鍵步驟解析
- 搜索空間的遍歷:通過回溯法逐步嘗試所有可能的分配方案。
- 約束過濾:利用
like
矩陣剪枝,排除不合法的分配。 - 狀態(tài)回溯:遞歸結(jié)束后,恢復(fù)當(dāng)前狀態(tài),繼續(xù)嘗試其他方案。
- 結(jié)果排序:所有方案按字典序輸出,滿足題目要求。
💯時(shí)間復(fù)雜度與空間復(fù)雜度分析
- 搜索空間規(guī)模: N ! N! N!(最大 120)。
- 剪枝操作:有效減少無(wú)效分配,優(yōu)化搜索效率。
- 排序復(fù)雜度: O ( M log ? M ) O(M \log M) O(MlogM),其中 M M M 是合法方案的數(shù)量。
整體時(shí)間復(fù)雜度為:
O ( N ! + M log ? M ) O(N! + M \log M) O(N!+MlogM)
空間復(fù)雜度為: O ( N ) O(N) O(N),用于存儲(chǔ)當(dāng)前狀態(tài)和遞歸棧。
💯理論拓展:回溯法的高級(jí)應(yīng)用
回溯法在約束滿足問題(CSP)中扮演核心角色,例如:
- N 皇后問題:將 N 個(gè)皇后放置在 N × N N \times N N×N 棋盤上,確保任意兩個(gè)皇后不互相攻擊。
- 數(shù)獨(dú)求解:填充數(shù)獨(dú)表格,滿足所有行、列和子區(qū)域的約束。
- 圖的著色問題:為圖的頂點(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í)踐的深入探索。