practice55｜第21章 动态规划自测

ONEPSOFT | 软考学习知识库

---

practice55｜第21章 动态规划自测

三题覆盖情境判断 / 概念辨析 / 综合连接。做完对照 " 教材依据 " 与 " 参考答案解读 "，再用底部自评表打分。

题目一（情境判断）

用逆序法求 A→B\{B1,B2}→C\{C1,C2}→E 的最短路。弧距离：A→B1=3,A→B2=5；B1→C1=4,C1→E=2；B2→C2=3,C2→E=6；B1→C2=7,B2→C1=8。请写出 f 值并给最短路径。

教材依据

逆序法：fₖ(Xₖ)=min\{本段距离 + 下阶段 f}；终点 f=0（到 E）；算到起点得全局最短。

参考答案解读

• f(C1)=2, f(C2)=6（C→E）。
• f(B1)=min(4+2, 7+6)=6（走 C1）；f(B2)=min(3+6, 8+2)=9（走 C2）。
• f(A)=min(3+6, 5+9)=min(9,14)=9（走 B1）。
• 最短路径：A→B1→C1→E，距离 = 3+4+2 = 9。

土木画像提示

像管路从 A 经两个中转段到 E：A 走 B1 再走 C1 到 E 总长 9，比走 B2 那条省。

---

题目二（概念辨析）

关于动态规划，下列说法正确的是（ ）

A. 动态规划每阶段只选 " 当前看起来最好 " 的决策（贪心）即可

B. 最短路用逆序法时 fₖ 取 max，资源分配时 fₖ 取 min

C. 逆序法从终点往回算每个点到终点的最优子值，再回代路径

D. 资源分配的状态转移 Sₖ₊₁=Sₖ−xₖ 表示 " 给了 xₖ 后剩余资源给后面 "

教材依据

动态规划管 " 当前 + 后续全局 " 最优（非贪心）；最短路 f 取 min、资源分配 f 取 max；逆序从终点回推；转移 Sₖ₊₁=Sₖ−xₖ。

参考答案解读

选 C、D。A 错：动态规划不是贪心，它用 f 值把 " 后续最优 " 也考虑进来；B 错：最短路 f 取 min、资源分配 f 取 max（距离最小、收益最大）；C 对；D 对。

土木画像提示

动态规划像 " 下棋看几步 "，不是走一步算一步；最短路求最短取 min，分资源求最大取 max；分出去的台班剩下的才给后面工序。

---

题目三（综合连接）

资源分配：总资源 S=4，分给甲、乙两项目（简化为 2 阶段），收益 v₁=\[0,3,5,6,8]，v₂=\[0,2,4,5,7]（x=0..4）。用 f₂(S)=v₂(S)，f₁(4)=max\_x₁\{v₁(x₁)+f₂(4−x₁)} 求最大总收益与分配。

教材依据

fₖ(Sₖ)=max\{vₖ(xₖ)+fₖ₊₁(Sₖ−xₖ)}；末项 f₂(S)=v₂(S)。

参考答案解读

• f₂=\[0,2,4,5,7]。
• f₁(4)=max：x₁=0→0+7=7；x₁=1→3+5=8；x₁=2→5+4=9；x₁=3→6+2=8；x₁=4→8+0=8。
• 最大总收益 = 9（x₁=2 → 甲得 2，余 2 给乙）。
• 校验：v₁(2)+v₂(2)=5+4=9 ✓。

土木画像提示

4 台班分给甲、乙：甲拿 2 台（产 5）、乙拿 2 台（产 4），总产出 9 最大；不是平均分，也不是全给一家。

---

自评表（做完打 √ / 打分）

维度	自评分（1-5）	备注
我会逆序法算最短路 f 值
我会回代最短路径
我理解 f 取 min（路）/ max（收益）
我会资源分配递推 fₖ
我会回代最优分配

低于 3 分的项目，回看 deepread55 的 ③ 段和 calculate55 分步解题再巩固一遍。