《算法设计与分析》期末试卷 (精选01)

一、单项选择题（每小题 2 分，共 15 题，30 分）

1. 二分搜索算法是利用（）实现的算法。

A. 分治策略
B. 动态规划法
C. 贪心法
D. 回溯法

查看答案与解析

答案：A

解析：

二分搜索（Binary Search）的关键思想是：把规模为 (n) 的问题拆成规模约为 (n/2) 的子问题，只在其中一个子区间继续搜索，直到找到目标或区间为空。
这满足“分解（divide）—解决（conquer）—合并（combine）”中的分解与递归求解结构（这里合并几乎是常数级判断），典型属于分治思想。

难度：⭐
考点：#二分查找 #分治

💡 学习锦囊

📖 相关公式与知识点

二分查找时间复杂度：(T(n)=T(n/2)+O(1)\Rightarrow T(n)=O(\log n)) :::

🔄 举一反三

已知有序数组长度为 (n)，二分查找最多比较多少次？
查看练习答案与解析
答案：(\lfloor \log_2 n \rfloor + 1) 次（或同量级）。
解析：每次将区间规模至少减半，直到区间长度为 1 或 0，比较次数等于把 (n) 反复除以 2 直到 (\le 1) 的次数。

2. 下列不是动态规划算法基本步骤的是（）。

A. 找出最优解的性质
B. 构造最优解
C. 算出最优解
D. 定义最优解（状态）

查看答案与解析

答案：A

解析：

动态规划经典流程（依据国内主流教材，如王晓东《算法设计与分析》）通常表述为：
1. 刻画最优子结构并建立状态（定义子问题/最优解的状态表示）；
2. 写出状态转移方程；
3. 选择自底向上或备忘录方式计算最优值；
4. 如需方案则记录决策并构造最优解。
说明：在 CLRS 等国外经典教材中，DP 步骤包含"刻画最优解的结构特征"（Characterize the structure of an optimal solution），与选项 A"找出最优解的性质"表述相近。但本题依据国内主流教材的步骤划分体系，将"分析最优解性质"归入问题分析阶段而非 DP 算法实现的基本步骤，故 A 为不属于标准步骤的项。

难度：⭐⭐
考点：#动态规划 #DP步骤

💡 学习锦囊

📖 相关公式与知识点

状态（state）、决策（decision）、转移（transition）、边界（base case）、最优值（optimal value）

🔄 举一反三

动态规划与分治法的关键区别是什么？
查看练习答案与解析
答案：动态规划要求子问题重叠并保存子问题结果；分治通常子问题相互独立，不必缓存。
解析：DP 通过“记忆化/表填充”避免重复计算；分治在独立子问题时不会造成指数级重复。

3. 回溯法解旅行售货员问题时的解空间树是（）。

A. 子集树
B. 排列树
C. 深度优先生成树
D. 广度优先生成树

查看答案与解析

答案：B

解析：

旅行售货员问题（TSP）要在所有城市访问顺序中找最短回路，本质是在所有“城市排列”中搜索，因此对应的解空间树是排列树。
子集树通常对应“选/不选”的组合型问题（如 0/1 背包的子集选择），而不是全排列。

难度：⭐
考点：#回溯 #TSP #排列树

💡 学习锦囊

📖 相关公式与知识点

子集树：每层“取/不取”，节点数 (O(2^n))
排列树：每层“选择一个未用元素”，节点数 (O(n!))

🔄 举一反三

0/1 背包问题用回溯法时通常对应哪类解空间树？
查看练习答案与解析
答案：子集树。
解析：每个物品只有“取/不取”两种决策，自然形成二叉子集树。

4. 下列算法中通常以自底向上的方式求解最优解的是（）。

A. 备忘录法
B. 动态规划法
C. 贪心法
D. 回溯法

查看答案与解析

答案：B

解析：

动态规划（表填充法）典型实现是自底向上：先算小规模子问题，再逐步得到大规模问题的最优值。
备忘录法通常是自顶向下递归 + 缓存（更接近“自顶向下”）。

难度：⭐
考点：#动态规划 #自底向上 #备忘录法

💡 学习锦囊

📖 相关公式与知识点

自底向上：循环填表
自顶向下：递归 + memo

🔄 举一反三

同一个 DP 问题可以既用自顶向下也用自底向上实现吗？
查看练习答案与解析
答案：可以。
解析：只要状态与转移一致，两种实现方式计算的是同一张“子问题—最优值”关系表。

5. 衡量一个算法好坏的核心指标是（）。

A. 运行速度快
B. 占用空间少
C. 时间复杂度低
D. 代码短

查看答案与解析

答案：C

解析：

算法评价的核心指标是时间复杂度与空间复杂度，其中时间复杂度通常作为首要度量标准；此外还需结合常数因素、可实现性等综合评判。
在本题选项中，"时间复杂度低"最贴近算法评价的核心指标。
A/B/D 都是片面或不严谨的描述：运行速度受硬件与实现影响，不能直接反映算法本身优劣；占用空间少仅是空间维度，不能单独作为衡量标准；代码短不等于算法优（如穷举法代码短但效率极低）。

难度：⭐
考点：#复杂度分析 #时间复杂度 #空间复杂度

💡 学习锦囊

📖 相关公式与知识点

渐进复杂度：忽略常数与低阶项，关注规模增长趋势

🔄 举一反三

时间复杂度与实际运行时间完全等价吗？
查看练习答案与解析
答案：不完全等价。
解析：复杂度描述的是输入规模变大时的增长趋势，常数因子、缓存命中、语言/编译优化等都会影响实际时间。

6. 下列算法中通常以深度优先方式系统搜索问题解的是（）。

A. 备忘录法
B. 动态规划法
C. 贪心法
D. 回溯法

查看答案与解析

答案：D

解析：

回溯法的典型框架是沿着解空间树“先走到底—再回退换分支”，即深度优先搜索（DFS）。

难度：⭐
考点：#回溯 #深度优先搜索

💡 学习锦囊

📖 相关公式与知识点

回溯 = DFS + 剪枝

🔄 举一反三

分支限界法通常对应哪种搜索策略？
查看练习答案与解析
答案：通常是广度优先或最佳优先（按界函数选择扩展节点）。
解析：分支限界法使用活结点表，按队列/优先队列组织。

7. 备忘录方法是那种算法的变形（）。

A. 分治法
B. 动态规划法
C. 贪心法
D. 回溯法

查看答案与解析

答案：B

解析：

备忘录法（Memoization）是动态规划的常见实现方式：采用自顶向下递归求解，并把已算过的子问题结果缓存起来，避免重复计算。

难度：⭐
考点：#动态规划 #备忘录 #记忆化搜索

💡 学习锦囊

📖 相关公式与知识点

记忆化搜索：递归时遇到已计算状态直接返回

🔄 举一反三

记忆化搜索为什么能把指数级递归降到多项式级？
查看练习答案与解析
答案：因为每个状态只计算一次。
解析：重复子问题被缓存命中消除，复杂度约等于“状态数 × 每次转移代价”。

8. 分支限界法解最大团问题时，活结点表的组织形式是（）。

A. 最小堆
B. 最大堆
C. 栈
D. 数组

查看答案与解析

答案：B

解析：

最大团（Maximum Clique）常用分支限界时，会用“上界”来决定优先扩展哪个活结点。
为了总是取“界值最大的结点”优先扩展，活结点表常用**最大堆（优先队列）**实现最佳优先搜索。

难度：⭐⭐
考点：#分支限界 #最大团 #优先队列 #最大堆

💡 学习锦囊

📖 相关公式与知识点

最佳优先：每次扩展界值最优的活结点

🔄 举一反三

若要优先取界值最小的结点，应使用什么数据结构？
查看练习答案与解析
答案：最小堆。
解析：最小堆能在 (O(\log n)) 时间取出当前最小键值元素。

9. 下面哪种函数是回溯法中为避免无效搜索采取的策略（）。

A. 递归函数
B. 剪枝函数
C. 随机数函数
D. 搜索函数

查看答案与解析

答案：B

解析：

回溯法的效率提升来自剪枝（Pruning）：当某个部分解不可能导向可行解或不可能优于当前最优解时，立即停止向下搜索。

难度：⭐
考点：#回溯 #剪枝

💡 学习锦囊

📖 相关公式与知识点

可行性剪枝：不满足约束则剪
最优性剪枝：上界 (\le) 当前最优则剪

🔄 举一反三

给出 0/1 背包回溯中一种常见上界估计方法。
查看练习答案与解析
答案：用“分数背包”的贪心装填求上界（线性松弛）。
解析：按单位价值从大到小装入，最后一个物品可取分数，得到一个不会低估的上界。

10. 矩阵连乘问题的算法可由（）设计实现。

A. 分支限界算法
B. 动态规划算法
C. 贪心算法
D. 回溯算法

查看答案与解析

答案：B

解析：

矩阵连乘（Matrix Chain Multiplication）具有最优子结构与重叠子问题，典型用 DP： [ m[i,j]=\min_{i\le k<j}{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j} ]

难度：⭐⭐
考点：#动态规划 #矩阵连乘 #区间DP

💡 学习锦囊

📖 相关公式与知识点

区间 DP：按区间长度递增填表

🔄 举一反三

矩阵连乘 DP 的状态是什么？
查看练习答案与解析
答案：(m[i,j]) 表示从第 (i) 个矩阵到第 (j) 个矩阵相乘的最少乘法次数。
解析：用断点 (k) 将区间 ([i,j]) 拆成两段，转移取最小。

11. 使用分治法求解不需要满足的条件是（）。

A. 子问题必须是一样的
B. 子问题不能够重复
C. 子问题的解可以合并
D. 原问题和子问题使用相同的方法解

查看答案与解析

答案：A

解析：

分治法要求：子问题与原问题结构相似（同类问题）、可递归求解、子问题解可合并。
子问题不必“完全一样”（例如快速排序左右子数组规模不同），只需是同一类结构问题即可。

难度：⭐⭐
考点：#分治 #分治条件

💡 学习锦囊

📖 相关公式与知识点

分治三步：分解、解决、合并

🔄 举一反三

归并排序满足分治的哪些条件？
查看练习答案与解析
答案：能分成两个子数组递归排序，且可在线性时间合并两个已排序数组。
解析：合并过程保证最终有序。

12. 下列算法中不能解决 0/1 背包问题的是（）。

A. 贪心法
B. 动态规划
C. 回溯法
D. 分支限界法

查看答案与解析

答案：A

解析：

0/1 背包每件物品只能取或不取，简单贪心（按单位价值、按价值、按重量）都可能失败，不能保证全局最优。
DP、回溯、分支限界都可求最优解（代价不同）。

难度：⭐⭐
考点：#0-1背包 #贪心反例 #动态规划

💡 学习锦囊

📖 相关公式与知识点

0/1 背包 DP：(dp[i][c]=\max(dp[i-1][c],dp[i-1][c-w_i]+v_i))

🔄 举一反三

哪种背包问题适合贪心法？
查看练习答案与解析
答案：分数背包（Fractional Knapsack）。
解析：允许取分数时，按单位价值排序贪心可证明最优。

13. 实现归并排序利用的算法是（）。

A. 分治策略
B. 动态规划法
C. 贪心法
D. 回溯法

查看答案与解析

答案：A

解析：

归并排序递归地将数组对半分解并分别排序，再线性合并两个有序序列，属于典型分治。

难度：⭐
考点：#归并排序 #分治

💡 学习锦囊

📖 相关公式与知识点

归并排序：(T(n)=2T(n/2)+O(n)\Rightarrow O(n\log n))

🔄 举一反三

快速排序为什么也属于分治？
查看练习答案与解析
答案：通过划分（partition）把问题分解为左右子数组递归求解。
解析：合并阶段不显式合并，但“划分 + 递归”仍是分治结构。

14. 下列是动态规划算法基本要素的是（）。

A. 定义最优解
B. 构造最优解
C. 算出最优解
D. 子问题重叠性质

查看答案与解析

答案：D

解析：

动态规划的适用关键在于：最优子结构 与 子问题重叠。
选项中只有“子问题重叠性质”属于 DP 的核心要素之一。

难度：⭐
考点：#动态规划 #子问题重叠 #最优子结构

💡 学习锦囊

📖 相关公式与知识点

若子问题互不重叠，分治即可；若大量重叠，DP/备忘录更优。

🔄 举一反三

Fibonacci 数列为何是“子问题重叠”的典型例子？
查看练习答案与解析
答案：递归式会重复计算相同的 (F(k))。
解析：如计算 (F(n)) 会多次调用 (F(n-2))、(F(n-3)) 等重复子问题。

15. 背包问题的贪心算法所需的计算时间为（）。

A. (O(n2^n))
B. (O(n\log n))
C. (O(2^n))
D. (O(n))

查看答案与解析

答案：B

解析：

背包“贪心算法”通常指分数背包：按单位价值排序（(O(n\log n))）后线性装入（(O(n))），总体为 (O(n\log n))。

难度：⭐
考点：#背包 #贪心 #排序复杂度

💡 学习锦囊

📖 相关公式与知识点

排序下界通常为 (O(n\log n))（比较排序模型）

🔄 举一反三

如果背包物品已按单位价值排好序，分数背包贪心时间复杂度是多少？
查看练习答案与解析
答案：(O(n))。
解析：无需排序，只需线性扫描装入。

二、简答题（每小题 6 分，共 7 题，42 分）

1. 请阐述大 (O) 算法复杂度的定义。

查看答案与解析

答案要点： 若存在正常数 (c>0) 与 (n_0)，使得当 (n\ge n_0) 时有 (f(n)\le c\cdot g(n))，则记 (f(n)=O(g(n)))。

解析（完整表述与理解）：

对象：大 (O) 描述的是“随输入规模 (n) 增长时”的渐进行为。
不等式含义：从某个规模 (n_0) 起，(f(n)) 被 (g(n)) 的某个常数倍上界住。
直观解释：忽略常数与低阶项后，(f(n)) 的增长“不会比 (g(n)) 更快”。
应用：用大 (O) 表示算法运行时间/空间与 (n) 的关系，便于不同算法比较。

难度：⭐
考点：#复杂度分析 #大O记号

💡 学习锦囊

📖 相关公式与知识点

(f(n)=O(g(n))) 是“上界”；相对地还有 (\Omega(\cdot))（下界）、(\Theta(\cdot))（紧确界）

🔄 举一反三

证明 (3n^2+2n+1 = O(n^2))。
查看练习答案与解析
答案：取 (c=6,n_0=1) 即可。
解析：当 (n\ge1) 时，(3n^2+2n+1 \le 3n^2+2n^2+n^2=6n^2)，所以为 (O(n^2))。

2. 请阐述回溯算法搜索子集树的一般模式。

查看答案与解析

答案要点（模板）： 在第 (i) 层对第 (i) 个元素做“选/不选”决策，深度优先递归；对不满足约束的部分解做剪枝；到叶子结点更新最优解或记录可行解。

解析（一般模式）：

状态/部分解：用向量 ((x_1,\dots,x_{i-1})) 表示前 (i-1) 个元素的选择情况。
扩展规则：到第 (i) 层时尝试 (x_i=1)（选）与 (x_i=0)（不选）两种分支。
可行性剪枝：若当前部分解已违反约束（如重量超限、冲突等），则不再向下扩展。
最优性剪枝：若对剩余部分做上界估计后仍不可能超过当前最优值，则剪枝。
终止条件：当 (i>n) 到叶结点时得到一个完整解，用于更新最优解或输出解集。

难度：⭐⭐
考点：#回溯 #子集树 #剪枝

💡 学习锦囊

📖 相关公式与知识点

子集树节点数上界：(2^n)，剪枝的作用是大量减少实际搜索

🔄 举一反三

子集树与排列树在分支数与节点规模上有何差异？
查看练习答案与解析
答案：子集树每层 2 分支，规模 (O(2^n))；排列树每层分支逐层递减，规模 (O(n!))。
解析：排列搜索更“爆炸”，剪枝更关键。

3. 请阐述分支限界搜索（广度优先搜索）算法的一般模式。

查看答案与解析

答案要点： 使用活结点表保存待扩展结点；按广度优先从队列取出一个活结点扩展其子结点；对子结点进行可行性检查与界函数剪枝；可行且可能改进最优解的子结点入队；直到活结点表为空。

解析（一般模式）：

结点含义：结点表示一个“部分解/状态”。
活结点表：广度优先常用队列（FIFO）。
扩展与生成：从队头取结点，生成其子结点（分支）。
界函数：为每个结点计算上界/下界，用于判断是否值得继续扩展。
最优解更新：遇到可行完整解则更新当前最优值，并据此更强地剪枝其它结点。

难度：⭐⭐
考点：#分支限界 #广度优先 #界函数

💡 学习锦囊

📖 相关公式与知识点

活结点组织：队列（BFS）、优先队列（最佳优先）、栈（DFS 风格）

🔄 举一反三

分支限界的“界”指的是什么？
查看练习答案与解析
答案：“界”指对当前部分解可能达到的最优值的估计（上界或下界）。解析：通过计算界值，可判断该分支是否有可能超过当前已知的最优解，从而决定是否剪枝。
:::

4. 请解释什么是贪心选择性质？什么是最优子结构性质？

查看答案与解析

答案要点：

贪心选择性质：全局最优解可以通过一系列局部最优（当前看起来最好的选择）逐步构造得到。
最优子结构性质：问题的最优解包含其子问题的最优解；把问题分解后，整体最优可由子问题最优组合得到。

解析（区分与联系）：

最优子结构是 DP 与贪心都常见的必要条件之一，但并不保证贪心可行。
贪心选择性质更强：它要求“第一步局部最优选择”必然出现在某个全局最优解中，因此可以不回溯地推进。
典型例子：
- 最优子结构：矩阵连乘、最短路径（Dijkstra 也用到了特殊结构）
- 贪心选择性质：活动选择、Huffman 编码、最小生成树等

难度：⭐⭐
考点：#贪心 #贪心选择性质 #最优子结构

💡 学习锦囊

📖 相关公式与知识点

许多反例说明：有最优子结构也未必能贪心（如 0/1 背包）

🔄 举一反三

为什么 0/1 背包不满足贪心选择性质？
查看练习答案与解析
答案：局部最优（单位价值最高）不一定属于全局最优组合。
解析：因为“取/不取”的离散性导致局部选择会占容量，阻碍更优的组合出现。

5. 请说明动态规划的基本步骤。

查看答案与解析

答案要点（标准步骤）：

定义状态（刻画子问题）；
写出状态转移方程；
确定边界条件与计算顺序（自底向上填表或自顶向下备忘录）；
计算最优值；
如需方案，记录决策并回溯构造最优解。

解析（为什么这么做）：

状态定义解决“子问题是什么”；转移方程解决“如何由小到大/由已知到未知”；边界与顺序确保不会用到未计算的状态；记录决策是为了输出具体方案而不仅是最优值。

难度：⭐
考点：#动态规划 #DP步骤

💡 学习锦囊

📖 相关公式与知识点

复杂度常估为：状态数 × 每个状态转移代价

🔄 举一反三

给出“最长公共子序列（LCS）”的状态与转移。
查看练习答案与解析
答案：令 (dp[i][j]) 表示 (X[1..i]) 与 (Y[1..j]) 的 LCS 长度；若 (X_i=Y_j)，(dp[i][j]=dp[i-1][j-1]+1)，否则 (dp[i][j]=\max(dp[i-1][j],dp[i][j-1]))。
解析：匹配时“共同增加”，不匹配时“舍弃一端”取最优。

6. 两机流水作业调度：若 (n=4)，在机器 M1 与 M2 上加工作业 (i) 的时间分别为 (a_i,b_i)，且

((a_1,a_2,a_3,a_4)=(4,5,12,10))，((b_1,b_2,b_3,b_4)=(8,2,15,9))。求最优调度方案并给出最优值。

查看答案与解析

**答案：**最优作业顺序为 (1,3,4,2)，最小完工时间（makespan）为 42。

解析（Johnson 法则，步骤完整）： 两机流水车间问题（(M_1\rightarrow M_2)）可用 Johnson 法则求最优序列：

在所有未排作业中找最小加工时间：在集合 ({a_i,b_i}) 中找最小值。
若最小值来自 (a_i)，把作业 (i) 安排在序列前端的最靠前空位；
若最小值来自 (b_i)，把作业 (i) 安排在序列后端的最靠后空位；
重复直到排完。

对本题：

所有时间最小为 (b_2=2)，来自 M2 ⇒ 作业 2 放在最后。
余下作业中最小为 (a_1=4)，来自 M1 ⇒ 作业 1 放在最前。
余下作业中最小为 (b_4=9)，来自 M2 ⇒ 作业 4 放在倒数第二。
剩余作业 3 放在中间。
得到序列：(1,3,4,2)。

计算完工时间（甘特计算）：

设 (C_1(j)) 为第 (j) 个作业在 M1 上完成时刻，(C_2(j)) 为在 M2 上完成时刻：

M1：
(C_1(1)=4)
(C_1(3)=4+12=16)
(C_1(4)=16+10=26)
(C_1(2)=26+5=31)
M2（每个作业在 M2 上开工时间为 (\max(C_1(\cdot),C_2(\text{前一作业})))）：
作业 1：开工 (4)，完成 (4+8=12)
作业 3：开工 (\max(16,12)=16)，完成 (16+15=31)
作业 4：开工 (\max(26,31)=31)，完成 (31+9=40)
作业 2：开工 (\max(31,40)=40)，完成 (40+2=42)

因此最小完工时间为 42。

难度：⭐⭐⭐
考点：#流水车间调度 #Johnson法则 #两机调度

💡 学习锦囊

📖 相关公式与知识点

两机 Johnson：可在 (O(n\log n))（排序实现）内得到最优序列

🔄 举一反三

若最小值同时出现在某个 (a_i) 与另一个 (b_j) 且相等，应如何处理？
查看练习答案与解析
答案：任选其一按规则放置即可（存在多最优解时会得到不同但同样最优的序列）。
解析：Johnson 规则的正确性不依赖唯一性。

7. 使用回溯法解 0/1 背包问题：(n=3)，(C=9)，(V={6,10,3})，(W={3,4,4})。要求用完全二叉树表示解空间（从根出发左 1 右 0），并求最优值与最优解。

查看答案与解析

**答案：**最优值 16，最优解向量 ((1,1,0))（选第 1、2 件物品）。

解析（解空间树 + 计算）：

解空间表示：长度为 3 的 0-1 向量 ((x_1,x_2,x_3))，其中 (x_i=1) 表示选第 (i) 件。根为空决策；每层决定一个 (x_i)。按题意：左分支取 1，右分支取 0。
枚举叶子（也可用剪枝，但本题规模小可直接列出）：

((1,1,1))：重量 (3+4+4=11>9)（不可行）
((1,1,0))：重量 (7)，价值 (6+10=16)（可行）
((1,0,1))：重量 (7)，价值 (9)（可行）
((1,0,0))：重量 (3)，价值 (6)（可行）
((0,1,1))：重量 (8)，价值 (13)（可行）
((0,1,0))：重量 (4)，价值 (10)（可行）
((0,0,1))：重量 (4)，价值 (3)（可行）
((0,0,0))：重量 (0)，价值 (0)（可行）

取最优：在所有可行解中价值最大者为 16，对应 ((1,1,0))。
解空间完全二叉树（文字版）：

第 1 层：(x_1=1)（左） / (x_1=0)（右）
第 2 层：分别扩展 (x_2=1/0)
第 3 层：分别扩展 (x_3=1/0) 得到上述 8 个叶子

难度：⭐⭐
考点：#0-1背包 #回溯 #子集树 #可行性剪枝

💡 学习锦囊

📖 相关公式与知识点

可行性剪枝：当前重量 (>C) 立即回溯
常用上界：分数背包上界用于最优性剪枝

🔄 举一反三

若用分数背包上界进行剪枝，本题在 ((1,1,*)) 处会发生什么？
查看练习答案与解析
答案：当选择到 ((1,1)) 后，剩余容量 (2)；若再尝试 (x_3=1) 会超重，直接剪枝该分支。
解析：可行性剪枝最直接；上界剪枝可进一步减少不必要探索。

三、算法设计及分析题（每小问 14 分，共 28 分）

1. 资金分配问题：现有资金 (a)（万元），计划分配给 (n) 个工厂扩大再生产。已知每个工厂利润 (g_i(x)) 与投资额 (x) 的关系已给定。

（1）设计最优投资方案并分析复杂度。
（2）用（1）的方法计算实例：总投资 50 万元，投资步长为 10 万元，利润函数如下表（注意：表格仅给出 (g_1\sim g_4)，据此本实例取 (n=4) 个工厂）。

利润\投资	10	20	30	40	50
g1(x)	20	50	65	80	85
g2(x)	20	40	50	55	60
g3(x)	25	60	85	100	110
g4(x)	25	40	50	60	65

查看答案与解析

（1）算法设计（动态规划）：

把资金离散成单位为 10 万元的整数份。令总资金为 (A)（单位：10 万元），本题 (A=5)。

状态定义：
(dp[i][j])：将 (j) 份资金分配给前 (i) 个工厂时可得到的最大利润。
转移方程：
设给第 (i) 个工厂分配 (k) 份（(0\le k\le j)），则： [ dp[i][j]=\max_{0\le k\le j}{dp[i-1][j-k]+g_i(10k)} ]
边界条件：
(dp[0][j]=0)（没有工厂利润为 0），(dp[i][0]=0)（资金为 0 利润为 0）。
最优方案恢复：
记录使转移取到最大值的 (k)（如用 (choice[i][j]) 记录），自 (i=n,j=A) 反推每个工厂获得的投资额。
复杂度分析：
状态数为 (n(A+1))，每个状态枚举 (k=0..j)（最多 (A+1) 次），因此时间复杂度： [ O(nA^2) ] 空间复杂度 (O(nA))（若滚动数组可降为 (O(A))）。

（2）实例计算（(n=4), (A=5)）：

将表中利润写成“份数 (k)”对应的值（(k=0..5)）：

(g_1)：[0,20,50,65,80,85]
(g_2)：[0,20,40,50,55,60]
(g_3)：[0,25,60,85,100,110]
(g_4)：[0,25,40,50,60,65]

我们给出一组最优分配结果（由 DP 转移或枚举均可验证）：

给工厂 1：20 万（(k_1=2)）利润 50
给工厂 2：0 万（(k_2=0)）利润 0
给工厂 3：30 万（(k_3=3)）利润 85
给工厂 4：0 万（(k_4=0)）利润 0

总投资 (20+0+30+0=50) 万，总利润 (50+0+85+0=135)。

最优值：135。
（说明：在所有满足 (k_1+k_2+k_3+k_4=5) 的组合中，最大利润为 135；例如 ((k_1,k_2,k_3,k_4)=(2,0,3,0)) 可达到最优。）

难度：⭐⭐⭐
考点：#动态规划 #资源分配 #最优化 #多阶段决策

💡 学习锦囊

📖 相关公式与知识点

多阶段决策常写成：阶段 (i)（第 (i) 个工厂），状态 (j)（剩余/已用资源），决策 (k)（本阶段分配量）

🔄 举一反三

若投资步长改为 5 万元，DP 的时间复杂度如何变化？
查看练习答案与解析
答案：若总资金仍 50 万，则 (A) 变为 10，时间从 (O(n\cdot 5^2)) 变为 (O(n\cdot 10^2))，约增加 4 倍。
解析：时间与 (A^2) 成正比。

《算法设计与分析》期末试卷 (精选01) ​

一、单项选择题（每小题 2 分，共 15 题，30 分） ​

1. 二分搜索算法是利用（ ）实现的算法。 ​

2. 下列不是动态规划算法基本步骤的是（ ）。 ​

3. 回溯法解旅行售货员问题时的解空间树是（ ）。 ​

4. 下列算法中通常以自底向上的方式求解最优解的是（ ）。 ​

5. 衡量一个算法好坏的核心指标是（ ）。 ​

6. 下列算法中通常以深度优先方式系统搜索问题解的是（ ）。 ​

7. 备忘录方法是那种算法的变形（ ）。 ​

8. 分支限界法解最大团问题时，活结点表的组织形式是（ ）。 ​

9. 下面哪种函数是回溯法中为避免无效搜索采取的策略（ ）。 ​

10. 矩阵连乘问题的算法可由（ ）设计实现。 ​

11. 使用分治法求解不需要满足的条件是（ ）。 ​

12. 下列算法中不能解决 0/1 背包问题的是（ ）。 ​

13. 实现归并排序利用的算法是（ ）。 ​

14. 下列是动态规划算法基本要素的是（ ）。 ​

15. 背包问题的贪心算法所需的计算时间为（ ）。 ​

二、简答题（每小题 6 分，共 7 题，42 分） ​

1. 请阐述大 (O) 算法复杂度的定义。 ​

2. 请阐述回溯算法搜索子集树的一般模式。 ​

3. 请阐述分支限界搜索（广度优先搜索）算法的一般模式。 ​

4. 请解释什么是贪心选择性质？什么是最优子结构性质？ ​

5. 请说明动态规划的基本步骤。 ​

6. 两机流水作业调度：若 (n=4)，在机器 M1 与 M2 上加工作业 (i) 的时间分别为 (a_i,b_i)，且 ​

7. 使用回溯法解 0/1 背包问题：(n=3)，(C=9)，(V={6,10,3})，(W={3,4,4})。要求用完全二叉树表示解空间（从根出发左 1 右 0），并求最优值与最优解。 ​

三、算法设计及分析题（每小问 14 分，共 28 分） ​

1. 资金分配问题：现有资金 (a)（万元），计划分配给 (n) 个工厂扩大再生产。已知每个工厂利润 (g_i(x)) 与投资额 (x) 的关系已给定。 ​

《算法设计与分析》期末试卷 (精选01)

一、单项选择题（每小题 2 分，共 15 题，30 分）

1. 二分搜索算法是利用（）实现的算法。

2. 下列不是动态规划算法基本步骤的是（）。

3. 回溯法解旅行售货员问题时的解空间树是（）。

4. 下列算法中通常以自底向上的方式求解最优解的是（）。

5. 衡量一个算法好坏的核心指标是（）。

6. 下列算法中通常以深度优先方式系统搜索问题解的是（）。

7. 备忘录方法是那种算法的变形（）。

8. 分支限界法解最大团问题时，活结点表的组织形式是（）。

9. 下面哪种函数是回溯法中为避免无效搜索采取的策略（）。

10. 矩阵连乘问题的算法可由（）设计实现。

11. 使用分治法求解不需要满足的条件是（）。

12. 下列算法中不能解决 0/1 背包问题的是（）。

13. 实现归并排序利用的算法是（）。

14. 下列是动态规划算法基本要素的是（）。

15. 背包问题的贪心算法所需的计算时间为（）。

二、简答题（每小题 6 分，共 7 题，42 分）

1. 请阐述大 (O) 算法复杂度的定义。

2. 请阐述回溯算法搜索子集树的一般模式。

3. 请阐述分支限界搜索（广度优先搜索）算法的一般模式。

4. 请解释什么是贪心选择性质？什么是最优子结构性质？

5. 请说明动态规划的基本步骤。

6. 两机流水作业调度：若 (n=4)，在机器 M1 与 M2 上加工作业 (i) 的时间分别为 (a_i,b_i)，且

7. 使用回溯法解 0/1 背包问题：(n=3)，(C=9)，(V={6,10,3})，(W={3,4,4})。要求用完全二叉树表示解空间（从根出发左 1 右 0），并求最优值与最优解。

三、算法设计及分析题（每小问 14 分，共 28 分）

1. 资金分配问题：现有资金 (a)（万元），计划分配给 (n) 个工厂扩大再生产。已知每个工厂利润 (g_i(x)) 与投资额 (x) 的关系已给定。