演算法推理：選教材，並證明最佳化答案
先說明模型、正確性和資源成本，再選演算法。本路線區分免費證明教材、廣泛的虛擬碼參考與偏重實際建模的伴讀；選一本主線，遇到明確問題再補讀另一種解釋，不把買齊三本等同於學會設計。
學習路線與例題編輯責任：University Reading List 編輯專案。 編輯與選書方法 · 來源核驗日期:
適用範圍與編輯責任
適合已學基礎程式設計、遞迴、資料結構和離散數學的大學讀者。Erickson明確假定這些準備，免費不等於零基礎程式書。下列排程資料、任務與答案為本站創作，不是出版社原題或工作場景實證。
選擇你的起點
三本書如何取捨
Algorithms
Jeff Erickson · 版次: 1 · 2019
免費證明與設計主線
- 適合何時選擇
- 已有歸納基礎，願意自己寫反例、論證和遞迴式。
- 何時另選路線
- 還需首次學習堆疊、雜湊表或程式語法。
- 建議閱讀範圍
- 2019版第1–4章，然後選讀第5–8章圖論。
- 限制與取捨
- 作者列出省略的先修資料結構，也不應讀者要求提供解答。免費正文不等於公開答案庫。
選書前試做
讀第3–4章後，用下方五任務說明最早結束規則為何可能不能最大化報酬。
檢查標準: 列出貪婪方案及報酬更高的可行方案，核對ID；不能用任務個數取代報酬目標。
演算法導論
Thomas H. Cormen et al. · 版次: 4 · 2022
範圍廣的第四版參考
- 適合何時選擇
- 課程指定CLRS，或需跨方法一致的虛擬碼。
- 何時另選路線
- 只需短導論，且尚不能選閱讀範圍或確認先修。
- 建議閱讀範圍
- 在第四版定位Dynamic Programming和Greedy Algorithms，按需回看分析與資料結構，以手中目錄為準。
- 限制與取捨
- 2022年所選精裝ISBN為9780262046305。教員受限資料不是自學者的公開解答權利，紙本標識也不含所有數位產品。
選書前試做
先用文字定義最佳化子問題，再說明最優後續決策可忽略哪些資訊。
檢查標準: 狀態定義應決定選項與基底；認得公式外形不等於證明最佳子結構。
演算法設計手冊
Steven S. Skiena · 版次: 3 · 2020
建模與實作伴讀
- 適合何時選擇
- 需要把應用敘述轉成組合問題並比較實作方向。
- 何時另選路線
- 希望只憑問題目錄或社群答案取代證明。
- 建議閱讀範圍
- 第三版實用設計部分，尤其第10章動態規劃；明確建模後再查目錄。
- 限制與取捨
- 作者站點的解答Wiki不保證社群答案正確。把它當成待檢查的論證，而非裁決。
選書前試做
將同一預約問題寫成生活敘述與帶權區間模型，列明相容條件和目標。
檢查標準: 每個現實條件要進入模型或明確排除；熟悉的名稱不能讓限制消失。
檢查先修準備
可行與最優有何不同？
可行是滿足全部限制；最優要與所有可行候選比較目標值。一個看似好的方案不能取代一般論證。
遞迴式為何需要歸納思路？
它連接已解的小問題與目前最優解，必須說明分類涵蓋所有可能。
時間複雜度要交代什麼？
定義n、輸入表示與所數操作；排序、前驅、填表和還原各自計成本。
六步學習與具體成果
已標記完成的成果: 0 / 6
勾選用於自我記錄，並非成績評定；標記不會傳送給本站。
-
先寫模型
建議閱讀範圍: Erickson第0章與Skiena建模討論。
動手產出: 寫清固定起訖、半開區間、報酬、單資源及總報酬目標。
檢查標準: 基本模型允許結束後立即接續，不含路程或準備時間。
-
反駁未證明的捷徑
建議閱讀範圍: Erickson第4章與CLRS貪婪法。
動手產出: 依最早結束執行，再找報酬更高的可行反例。
檢查標準: 展示所選ID；反例否定特定普遍主張，不代表所有貪婪法失敗。
-
定義狀態
建議閱讀範圍: Erickson第3章與CLRS動態規劃。
動手產出: 依結束排序，用完整句子解釋V(j)、p(j)。
檢查標準: V(j)限前j任務；p(j)是相容的最後前任務，沒有則為0。
-
計算並說明表格
建議閱讀範圍: 同一動態規劃範圍。
動手產出: 逐行比較兩選項，記錄前驅並還原方案。
檢查標準: 最優解不是不含j，就是含j及相容前綴最優解；說明分類完整。
-
改變一項限制
建議閱讀範圍: Skiena第10章與變式。
動手產出: 加入規定間隔，重算相容性後再用遞迴式。
檢查標準: 即使報酬與式子外形不變，p陣列改變仍可能使舊解不可行。
-
提交可檢核的成果
建議閱讀範圍: 回到最弱步驟對應教材。
動手產出: 提交模型、反例、表格、還原、複雜度和邊界檢驗。
檢查標準: 他人能重算報酬與可行性；一次小程式計時不是漸近分析。
原創例題與解析
原創例題：最早結束不會最大化報酬
五個虛構任務的(開始,結束,報酬)為a=(0,3,5)、b=(3,5,4)、c=(0,5,12)、d=(5,7,3)、e=(4,8,11)。一份資源只能執行不重疊任務。求最大報酬並比較最早結束法。
前提假設
採半開區間，允許結束後立即接續；時刻固定、不可拆分、非負報酬相加。無準備間隔、路程或不確定性。同結束時刻排b再c，改變表次序而不改最優值。
- 最早結束選a、b、d，得5+4+3=12；可行的a、e得16，所以該規則不能一般地解帶權目標。
- 順序a、b、c、d、e的p=[0,1,0,3,1]。V(0)=0，V(j)=max(V(j−1),reward(j)+V(p(j)))，分別表示不選與選j。
- V=[0,5,9,12,15,16]。末行選e，回到前驅a，11+5=16。
- 排序和二分搜尋前驅可用O(n log n)，填表與還原O(n)，儲存O(n)。有限資料檢驗與一般論證應區分。
答案與解釋
最大值16由a與e取得；三任務貪婪方案得12。個數與報酬是不同目標。
檢驗結果
獨立列舉32個子集並排除不相容者，應得同一最優值。還原後仍須查端點，不只相信表值。
改變假設，再做一題
變式：任務之間必須保留間隔
保留任務與報酬，但相鄰被選任務間至少留2個時間單位。最後任務後不需間隔，時刻不可移動。
- 相容條件為finish(i)+2≤start(j)，p=[0,0,0,1,0]。a可接d，卻不能接b或e。
- 新V=[0,5,5,12,12,12]。c單獨得12；舊a、e因3+2>4不可行。
答案與解釋
新最優值是c單獨的12。保留遞迴式並重建相容資料；從舊報酬扣固定費用是別的模型。
檢驗結果
依新條件重列舉；單一任務不需末尾間隔。舊最優值是放寬限制後的上界，不是此處的可行答案。
常見誤區
把虛擬碼當證明
本例程式算對，不表示對所有輸入正確。區分有限測試與一般論證。
以名稱取代模型
準備時間可能破壞熟悉的歸約；先說明排除的條件。
只計部分複雜度
不能忽略排序或平方級前驅掃描，再稱全實作線性；上界須對應實作。
進入下一階段之前
- 能明確說明目標與全部相容規則。
- 能解釋遞迴式並還原可行方案。
- 能改一項假設，指出須改的資料或論證。
來源與版次核驗
來源核驗日期:
- Jeff Erickson: 2019 edition, prerequisites and chapter files
著者資料核實2019版、免費正文、先修與章序；試做和資料由本站創作。
- MIT Press: Introduction to Algorithms, fourth edition
出版社確認第四版、2022年與紙本/電子不同標識；不承諾受限教員資料。
- Springer: The Algorithm Design Manual, third edition
出版社支持實用設計和參考範圍；選書判斷不是學習效果實測。
- Author-hosted third-edition chapter and solution index
作者站點確認動態規劃位置並說明社群答案未獲認證。
這些是本站建議的學習活動，並非大學官方作業，也不代表對每本書逐頁通讀。