简介：这份资源是西南交通大学人工智能专业「算法分析与设计」课程的作业与实验全集，面向正在修读或准备复习该课程的学生，以及需要参考算法实现与实验报告的学习者。内容覆盖排序、搜索、图论、动态规划等核心算法领域，并包含实验课程的代码实现与文档说明，可帮助读者对照课程要求完成作业、理解算法复杂度分析并优化程序。资源包共28个文件，以zip压缩包为主，另含docx、doc、pdf文档及cpp源码和txt说明，整体约13.69MB，结构清晰，便于按作业与实验模块分类查阅。目前已有1753人学习下载，适合需要系统梳理课程重点、参考实验步骤与排错思路的学习者使用。

1. 算法分析与设计这门课，为什么让这么多人在实验环节翻车

西南交通大学算法分析与设计这门课，理论卷面能背，实验环节却经常卡住——这是我在带低年级同学做课程作业时最直观的感受。标题里说的“作业全集附带答疑”，本质上不是一份答案合集，而是一套把课堂伪代码翻译成可提交代码的工程流程：分治、动态规划、贪心、回溯、分支限界、图算法这几大块，每一块都要落到具体输入输出、时间限制和测试用例上。适合谁？正在修这门课、被实验报告和 OJ 判题卡住的本科生，以及想用 Python 或 C++ 把经典算法真正跑一遍的转码同学。它解决的不是“懂不懂原理”，而是“为什么我的代码本地过、提交就超时或答案错”这类落地问题。

2. 先搞清楚作业全集里到底有哪几类题

2.1 理论作业和实验作业的边界在哪

很多人把“作业全集”理解成一份可以直接抄的答案文档，这个预期一开始就偏了。西南交大这门课的考核通常分两层：理论作业考的是复杂度推导、递推式求解、算法正确性证明，答案形态是公式和文字；实验作业考的是给定问题规模下的可运行程序，答案形态是源码加运行结果。两者共用同一套算法思想，但评分标准完全不同。理论题写错一个渐进符号可能只扣两分，实验题数组越界直接零分。所以拿到任何一份作业材料，第一件事是按“是否需要提交可执行文件”把它分成两堆，而不是按章节顺序从头做。

我一般会建议先扫一遍实验指导书里每道题的输入输出格式说明。算法分析与设计的实验题有个特点：题目描述往往很短，但输入输出约束写得很死，比如“第一行输入 n，接下来 n 行每行两个整数”。这些约束才是真正决定你代码结构的東西，而不是题目名字叫“背包问题”还是“最长公共子序列”。

2.2 分治、DP、贪心、回溯在实验里各占什么位置

从历年实验题的分布看，动态规划和回溯是重灾区，分治和贪心相对好拿分。原因不复杂：DP 的状态定义和转移方程一旦想歪，代码写得再漂亮也是错的，而且本地小样例还测不出来；回溯的剪枝条件写不好，规模稍微大一点就超时。分治的典型题是归并排序求逆序对、最近点对，模板性强，背下来就能用。贪心的难点在证明，但实验环节通常只要求你实现，不要求你写证明，所以反而轻松。

这里有个选型判断：如果一道题你读完第一反应是“每一步选当前最好的”，先别急着写贪心，用反例试一下。找不出反例再用贪心，找得出就老老实实上 DP。这个习惯能帮你省掉大量“写完才发现思路错了”的时间。

2.3 一份可复用的实验代码目录结构

不管用什么语言，我建议按下面的结构组织你的实验代码，后面调试和复用会省很多事：

algo-lab/ ├── common/ │ ├── io_helper.py # 统一输入输出解析 │ └── timer.py # 计时装饰器，用于对比复杂度 ├── divide_conquer/ │ ├── merge_sort.py │ └── closest_pair.py ├── dp/ │ ├── knapsack.py │ └── lcs.py ├── greedy/ │ └── activity_select.py ├── backtracking/ │ ├── n_queens.py │ └── subset_sum.py └── tests/ └── cases/ # 存放每道题的测试输入输出

这个结构的好处是：common里的输入解析和计时工具只写一次，每道新题直接调用；tests/cases让你可以脱离 OJ 在本地批量验证。很多同学每道题都从input()重新写起，改一个格式就要动所有文件，这是纯浪费。

3. 动态规划实验题：从状态定义到滚动数组的完整落地

3.1 状态定义错了，后面全白写

DP 实验题翻车，九成死在状态定义。以最经典的 0-1 背包为例，很多人上来就写dp[i]表示“前 i 个物品能装的最大价值”，然后发现容量维度丢了，转移方程根本写不出来。正确的定义是dp[i][j]：前 i 个物品、容量为 j 时的最大价值。这个定义里两个维度缺一不可，因为“能不能再装一个物品”同时取决于已经考虑了多少物品和还剩多少容量。

状态定义有个自检方法：看你的转移方程里用到的所有变量，是不是都能从状态的下标里读出来。如果转移时还需要一个“当前剩余容量”这种没出现在下标里的量，说明状态定义漏了维度。这个检查花不了十秒，但能拦住大部分低级错误。

3.2 0-1 背包的二维到一维优化代码

先看二维版本，逻辑最清晰：

def knapsack_2d(weights, values, capacity): n = len(weights) # dp[i][j]: 前 i 个物品，容量 j 下的最大价值 dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): w, v = weights[i - 1], values[i - 1] for j in range(capacity + 1): if j < w: # 装不下，只能不选 dp[i][j] = dp[i - 1][j] else: # 选或不选取较大值 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v) return dp[n][capacity]

逻辑说明：外层循环遍历物品，内层遍历容量。dp[i][j]只依赖dp[i-1]这一行，所以二维可以压成一维。参数上，weights和values等长，capacity是背包总容量，返回最大价值。

一维优化版本：

def knapsack_1d(weights, values, capacity): # dp[j]: 容量 j 下的最大价值 dp = [0] * (capacity + 1) for w, v in zip(weights, values): # 必须倒序遍历，保证每个物品只用一次 for j in range(capacity, w - 1, -1): dp[j] = max(dp[j], dp[j - w] + v) return dp[capacity]

这里最关键的一行是range(capacity, w - 1, -1)。倒序是为了保证计算dp[j]时用到的dp[j-w]还是上一轮（没考虑当前物品）的值。如果写成正序，就变成了完全背包，每个物品可以重复选，答案会偏大。这个坑我在批改实验报告时见过太多次，代码看起来没问题，结果就是不对，原因全在这个循环方向。

3.3 用计时器验证复杂度有没有真的降下来

优化完别急着提交，用计时器实测一下。下面这个装饰器可以直接复用：

import time from functools import wraps def timer(func): @wraps(func) def wrapper(*args, **kwargs): start = time.perf_counter() result = func(*args, **kwargs) elapsed = time.perf_counter() - start print(f"{func.__name__} 耗时 {elapsed:.4f}s") return result return wrapper

参数说明：time.perf_counter()比time.time()精度高，适合测毫秒级差异。用法就是给knapsack_1d加上@timer装饰器，然后构造一组 n=100、capacity=1000 的随机数据跑一遍。如果一维版本没有明显快于二维版本，先检查你的数据规模是不是太小——小规模下两者差异被常数项淹没，看不出优化效果。一般 n 上到 500 以上，空间优化带来的缓存友好性才会体现出来。

4. 回溯与分支限界：剪枝写不对就是纯暴力

4.1 N 皇后问题的冲突检测优化

N 皇后是回溯的入门题，但实验题往往会加大 N 来卡人。朴素写法每次放皇后都遍历已放置的皇后检查冲突，复杂度是 O(N) 每次，整体下来常数很大。优化做法是用三个布尔数组分别记录列、主对角线、副对角线是否被占用：

def solve_n_queens(n): cols = [False] * n diag1 = [False] * (2 * n - 1) # 主对角线，i - j + n - 1 diag2 = [False] * (2 * n - 1) # 副对角线，i + j result = [] def backtrack(row, placement): if row == n: result.append(placement[:]) return for col in range(n): d1 = row - col + n - 1 d2 = row + col if cols[col] or diag1[d1] or diag2[d2]: continue # 做选择 cols[col] = diag1[d1] = diag2[d2] = True placement.append(col) backtrack(row + 1, placement) # 撤销选择 placement.pop() cols[col] = diag1[d1] = diag2[d2] = False backtrack(0, []) return result

逻辑说明：row - col + n - 1把主对角线映射到[0, 2n-2]，同一主对角线上的格子这个值相等；row + col同理处理副对角线。这样冲突检测从 O(N) 降到 O(1)。参数上，n是棋盘大小，返回所有解的列表，每个解是一个长度为 n 的数组，第 i 个元素表示第 i 行皇后所在的列。

4.2 子集和问题的可行性剪枝

子集和问题给一个数组和一个目标值，判断能否选出若干数之和等于目标。纯回溯会枚举 2^n 种组合，必须剪枝。两个有效的剪枝方向：一是排序后如果当前和已经超过目标就停止（因为后面的数只会让和更大）；二是预处理后缀和，如果当前和加上剩余所有数都达不到目标，也停止。

def subset_sum(nums, target): nums.sort() n = len(nums) # suffix[i]: 从 i 到末尾所有数之和 suffix = [0] * (n + 1) for i in range(n - 1, -1, -1): suffix[i] = suffix[i + 1] + nums[i] def dfs(idx, current): if current == target: return True if idx == n or current > target: return False # 剪枝：剩余全部加上也不够 if current + suffix[idx] < target: return False # 选 nums[idx] if dfs(idx + 1, current + nums[idx]): return True # 不选 nums[idx] return dfs(idx + 1, current) return dfs(0, 0)

参数说明：nums是候选数字列表，target是目标和，返回布尔值。suffix数组是剪枝的核心，没有它，当目标远大于数组总和时程序会白跑完所有分支。注意排序是必须的，否则current > target这个剪枝不成立——因为未排序时后面的数可能更小，当前和超了不代表后面不能把它拉回来。

4.3 分支限界和回溯在实验评分上的差别

分支限界和回溯经常被混为一谈，但实验评分时它们的区别很实际。回溯是深度优先，找到解就返回，适合“求所有解”或“判断可行性”；分支限界用优先队列按界函数排序，适合“求最优解”，比如带权活动选择、旅行商问题的近似。如果你在“求最优解”的题里用了纯回溯，规模一大就超时；反过来在“求所有解”的题里用分支限界，代码复杂度上去了但没收益。判断标准很简单：题目问“有多少种”或“是否存在”用回溯，问“最大/最小是多少”用分支限界。

5. 避坑与排查：实验提交前必须过的五道关

5.1 本地样例过、OJ 报答案错误

现象：自己构造的测试用例输出正确，提交后返回 WA。原因通常是边界条件没覆盖，比如 n=0、数组为空、目标值等于 0 这些情况。解决：在tests/cases里专门放一组边界输入，每次改完代码先跑边界组。我习惯在每道题的主函数开头加一句if not nums: return 0之类的防御，成本极低。

5.2 递归深度超限导致运行时错误

现象：回溯题在 N 稍大时抛RecursionError或段错误。原因：Python 默认递归深度约 1000，C++ 栈空间也有限。解决：Python 里sys.setrecursionlimit(100000)，但更稳妥的是把回溯改成显式栈的迭代写法。如果题目规模确实大，迭代是唯一出路，别指望调递归上限能救。

5.3 输入解析格式不匹配

现象：本地用input().split()读得好好的，提交后第一个测试点就 RE。原因：OJ 的输入可能有多余空行、行末空格，或者数据分布在不同行。解决：统一用sys.stdin.read().split()一次性读入所有 token，再按顺序取，这样对换行和空格都不敏感。这个改动几乎能消灭所有输入格式类错误。

5.4 DP 数组初始化漏掉负值情况

现象：求最大值的 DP 题，答案比正确值偏大。原因：初始化用了 0，但某些状态实际不可达，应该初始化为负无穷。解决：明确哪些状态是“合法可达”的，不可达的初始化为-inf（Python 用float('-inf')）。0-1 背包里dp[0][j]=0是对的，但换成“恰好装满”的变体就不对了，必须dp[0][0]=0、其余-inf。

5.5 贪心题没验证反例就提交

现象：贪心策略看起来合理，但部分测试点 WA。原因：贪心选择性质没成立，局部最优不等于全局最优。解决：写完贪心后，用 n=3 到 n=5 的小规模数据暴力枚举所有方案，和贪心结果对比。对不上就说明贪心错了，赶紧换 DP。这个暴力对拍脚本写一次能用一学期。

6. 把作业全集变成自己的算法模板库

做完整套作业，最有价值的不是那些提交记录，而是你从中沉淀下来的模板。我的习惯是每做完一道题，把可复用的部分抽到common或对应分类目录下，并且写一句注释说明适用条件。比如二分查找的边界处理、并查集的路径压缩、Dijkstra 的优先队列写法，这些在后续课程和面试里会反复用到。

验证模板是否真的可用，有个简单方法：拿一道新题，只允许自己从模板库复制代码，不允许重新写。如果拼装出来的程序能过，说明模板抽象得够干净；如果发现某个模板总是要改，那说明它的接口设计有问题，回去重构。这个“只用模板解题”的练习，比刷十道新题更能提升工程能力。

最后一个具体技巧：给每个模板写一个最小测试用例，放在文件末尾的if __name__ == "__main__":里。这样你半年后回头看，不用回忆输入格式，直接运行文件就知道模板还能不能用。我吃过这个亏——当时觉得代码简单没写测试，复习时对着一个并查集模板愣了十分钟才想起来参数顺序。从那以后，每个模板必带自测，这个习惯帮我省下的时间远超写测试的成本。希望帮到你。

本文还有配套的精品资源，点击获取