1. 项目概述当数学建模遇上动态规划如果你参加过数学建模竞赛或者处理过一些复杂的优化决策问题大概率会听过“动态规划”这个名字。它不像线性规划那样有现成的求解器可以一键调用也不像神经网络那样充满神秘感但它在解决一类特定问题上展现出的简洁与高效常常让人拍案叫绝。简单来说动态规划是一种解决多阶段决策过程最优化问题的数学方法。它的核心思想非常“聪明”把一个大问题分解成一系列相互关联的小问题通过解决这些小问题并记住它们的答案专业术语叫“存储中间状态”来避免重复计算最终高效地得到全局最优解。这听起来有点抽象我举个生活中最常见的例子你就明白了找零钱。假设我们有面值为1元、5元、10元的硬币现在要凑出18元并且要求硬币数量最少。最笨的方法是枚举所有可能的组合比如10个1元、1个5元加13个1元……这显然计算量巨大。而动态规划的思路是我们从凑1元开始想凑1元最少需要1个1元硬币。凑2元呢可以是两个1元所以是2个。我们一步步记录下凑出1元、2元、3元……直到18元所需的最少硬币数。在计算凑18元时我们不需要重新从头枚举只需要考虑三种情况用1个1元硬币加上“凑17元的最优方案”、用1个5元硬币加上“凑13元的最优方案”、用1个10元硬币加上“凑8元的最优方案”。然后从这三种情况里选一个硬币数最少的。你看我们直接利用了之前计算好的“凑17元”、“凑13元”、“凑8元”的结果这就是动态规划“记住过去”的威力。在数学建模中动态规划的应用场景极其广泛。从经典的资源分配、生产调度、最短路径问题到近年来竞赛中出现的无人机路径规划、能源系统优化、投资策略选择凡是涉及“分阶段决策”和“寻求全局最优”的问题动态规划都可能成为一把利器。很多同学觉得动态规划难主要是卡在了两个地方一是如何把实际问题抽象成动态规划的模型即定义“状态”和“决策”二是如何写出高效无误的递推代码。这篇笔记我就结合自己多年带队和评审的经验把动态规划从核心思想到建模实战掰开揉碎了讲清楚让你不仅能看懂更能用起来。2. 动态规划核心思想与建模框架拆解动态规划之所以强大在于它有一套严谨的思维框架。掌握这个框架比死记硬背几个算法模板要有用得多。整个框架可以概括为四个关键步骤和两个核心要素。2.1 理解“最优子结构”与“无后效性”这是动态规划能够成立的理论基石必须首先吃透。最优子结构指的是一个问题的最优解包含了其子问题的最优解。换句话说我们可以通过子问题的最优解来构造出原问题的最优解。比如前面找零钱的例子凑18元的最优方案假设是105111那么它里面用到的“凑8元”对应10元之后剩下的8元的方案也必须是凑8元这个问题的最优方案。如果“凑8元”有更优的方案比如两个5元加两个1元但这里不对仅举例那么整个凑18元的方案就可以被替换成更优的这就矛盾了。因此原问题的最优解必须由子问题的最优解构成。无后效性也叫“马尔可夫性质”意思是未来的状态只取决于当前的状态而与如何到达当前状态的路径无关。一旦当前状态确定了后续的决策过程就和之前的历史无关了。在找零钱问题里“当前拥有多少钱”就是一个状态。当我们处于“还需要凑8元”这个状态时我们只需要关心如何从8元这个状态继续凑出零钱而不需要关心这8元是之前怎么剩下来的是通过用了10元还是5元剩下来的。这个性质保证了我们可以放心地存储并复用每个状态下的最优解而不用担心历史决策的影响。很多建模问题无法直接用动态规划就是因为不满足这两个性质之一。比如一些博弈问题对手的行动会受我方历史行动影响就具有“后效性”。再比如一些网络流问题可能不满足最优子结构。在选题时快速判断问题是否具备这两个性质是决定能否采用动态规划的第一步。2.2 动态规划建模四步法将一个实际问题转化为动态规划模型通常遵循以下四个步骤。我们以一个经典的数学建模赛题简化版为例来说明某工厂要制定一个季度3个月的生产计划。已知每月初的库存量、每月的市场需求量、每月的生产能力上限、单位产品的生产成本和库存成本。目标是制定一个总成本最低的生产计划。第一步划分阶段将问题过程恰当地划分为若干个相互联系的阶段。阶段通常是按时间或空间顺序划分的。在我们的生产计划问题中很自然地可以按月份将整个过程划分为3个阶段k1,2,3每个阶段初需要做出本月生产量的决策。第二步定义状态状态是对过程当前情况的描述它既是该阶段决策的起点又包含了之前决策的历史信息。状态的选择必须满足无后效性。在这个问题里每个阶段初即做决策时的库存量s_k是一个关键的状态变量。因为本月要生产多少不仅取决于本月需求还取决于月初有多少库存。状态变量s_k完整地概括了历史未来的成本只与当前库存s_k和后续决策有关。第三步确定决策变量与状态转移方程在每个阶段当状态给定后可以做出决策决策会影响到下一阶段的状态。决策变量就是我们在每个阶段可以控制的因素。这里决策变量是第k个月的生产量x_k。它受到生产能力上限和需求约束。 状态转移方程描述了从当前状态s_k和决策x_k如何得到下一阶段状态s_{k1}。这是一个确定性关系。在本例中状态转移方程很简单s_{k1} s_k x_k - d_k其中d_k是第k个月的市场需求量。它表示下月初的库存等于本月初库存加上本月产量再减去本月销量。第四步建立指标函数与递推方程指标函数是衡量过程优劣的数量指标。我们最终要优化的是总成本它是一个多阶段指标函数。动态规划的核心是找到这个指标函数的递推关系。 设v_k(s_k, x_k)为第k阶段处于状态s_k采用决策x_k所产生的阶段成本包括生产成本和库存成本。 设f_k(s_k)表示从第k阶段开始初始库存为s_k采用最优策略到达过程结束时的最小总成本。这就是我们要求的“最优值函数”。 递推方程通常采用逆序递推如下f_k(s_k) min_{x_k} { v_k(s_k, x_k) f_{k1}(s_{k1}) }边界条件为f_4(s_4) 0计划期结束后无论剩下多少库存其未来成本为0或者可以根据实际情况设定一个残值。 这个方程的意思是从k阶段状态s_k出发的最小总成本等于对所有可能的决策x_k取“当前阶段成本”加上“从下一阶段新状态s_{k1}出发的最小总成本”之和的最小值。注意这里演示的是逆序递推即从最后一个阶段倒推到第一个阶段。也有顺序递推取决于问题描述和边界条件的设定。在建模论文中必须清晰地说明你采用的是顺序还是逆序并给出递推方程的完整数学形式。3. 经典模型解析与代码实现要点理解了理论框架我们来看几个数学建模中最常遇到的动态规划模型。我会给出它们的模型抽象、递推方程并重点说明用代码实现时的关键点和易错点。3.1 背包问题资源分配的基石背包问题是动态规划的入门课也是很多资源分配问题的原型。其基本描述是有一个容量为V的背包和N件物品每件物品有体积w_i和价值c_i。如何选择物品装入背包使得总价值最大。1. 0-1背包模型这是最基础的模型每件物品最多选一次。定义状态f[i][j]表示考虑前i件物品在背包容量为j的情况下能获得的最大价值。 状态转移方程f[i][j] max(f[i-1][j], f[i-1][j-w[i]] c[i]) if j w[i]f[i][j] f[i-1][j] if j w[i]这个方程的含义是对于第i件物品有两种决策——不选它则价值等于前i-1件物品在容量j下的最优解选它则价值等于“前i-1件物品在容量j-w[i]下的最优解”加上物品i的价值。两者取最大。代码实现要点Pythondef zero_one_pack(N, V, w, c): # 初始化dp数组全为0 dp [[0] * (V 1) for _ in range(N 1)] for i in range(1, N 1): # 遍历物品 for j in range(1, V 1): # 遍历容量 if j w[i-1]: # 注意w和c的索引从0开始 dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i-1]] c[i-1]) else: dp[i][j] dp[i-1][j] return dp[N][V] # 空间优化滚动数组 def zero_one_pack_opt(N, V, w, c): dp [0] * (V 1) # 一维数组dp[j]表示容量为j时的最大价值 for i in range(N): # 注意内层循环必须逆序这是0-1背包空间优化的关键。 for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] c[i]) return dp[V]实操心得0-1背包的空间优化版本一维数组中内层循环必须逆序从V到w[i]。这是因为每个物品只能选一次逆序可以保证在更新dp[j]时用到的dp[j - w[i]]是上一轮即考虑前i-1件物品时的值。如果是正序dp[j - w[i]]可能在本轮已经被更新过相当于物品被重复选取这就变成了完全背包问题。这是新手最容易栽跟头的地方。2. 完全背包模型与0-1背包的唯一区别是每件物品可以选无限次。状态定义相同但转移方程有细微差别f[i][j] max(f[i-1][j], f[i][j-w[i]] c[i]) if j w[i]注意第二个项是f[i][j-w[i]]而不是f[i-1][j-w[i]]。这是因为物品i可以重复选所以在考虑容量j时可能已经选过若干个物品i了因此应该从“考虑过物品i、容量为j-w[i]”的状态转移过来。代码实现要点def complete_pack_opt(N, V, w, c): dp [0] * (V 1) for i in range(N): # 关键点内层循环正序 for j in range(w[i], V 1): dp[j] max(dp[j], dp[j - w[i]] c[i]) return dp[V]注意完全背包的一维优化代码内层循环是正序的。这正是因为允许重复选择所以用本轮更新过的值来更新更大的容量是合理的。对比0-1背包和完全背包的代码只有内层循环的顺序不同但背后的逻辑天差地别务必理解透彻。3.2 最长子序列问题序列分析的利器这类问题在时间序列分析、DNA序列比对、文本相似度比较等场景中广泛应用。最长上升子序列LIS是代表。问题描述给定一个长度为N的数列a求它的一个最长上升子序列的长度子序列不一定连续但顺序必须与原序列相同。动态规划定义定义dp[i]为以第i个数字结尾的最长上升子序列的长度。 状态转移方程dp[i] max(dp[j]) 1, 对于所有 j i 且 a[j] a[i]如果不存在这样的j则dp[i] 1。 最终答案是max(dp[0...N-1])。代码实现与优化def length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n # 每个元素本身至少是一个长度为1的LIS for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) # 优化版本贪心二分查找O(nlogn) def length_of_lis_opt(nums): d [] # d是一个单调递增的数组d[i]表示长度为i1的LIS的末尾元素的最小值 for num in nums: if not d or num d[-1]: d.append(num) else: # 二分查找找到第一个大于等于num的位置将其替换为num left, right 0, len(d) - 1 loc right while left right: mid (left right) // 2 if d[mid] num: loc mid right mid - 1 else: left mid 1 d[loc] num return len(d)实操心得基础的O(n^2)解法在建模中用于理解原理完全足够代码也简单。但如果数据量较大n 5000就必须考虑O(nlogn)的优化版本。这个优化版本的思想很巧妙维护一个数组dd[i]存储所有长度为i1的上升子序列中末尾元素的最小值。由于d是单调递增的我们可以用二分查找来更新它。这个算法通常不会要求推导但作为已知的高效算法直接使用并在论文中引用其思想是加分项。3.3 最短路径问题图论中的动态规划动态规划在图论中有一个非常著名的应用——求解多阶段图的最短路径以及更一般的Floyd-Warshall算法虽然它常被归为图论算法但其本质是动态规划。多阶段图最短路径将图划分为若干个阶段每个阶段的决策是选择走向下一个阶段的哪个节点。定义f[i][j]为从起点到达第i阶段j节点的最短路径长度。其递推关系通常很直观。Floyd算法用于求解任意两点间的最短路径。定义dp[k][i][j]表示只允许使用前k个节点作为中间节点时从i到j的最短路径长度。其状态转移方程为dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])通过滚动数组可以优化掉第一维得到我们常见的三重循环形式。代码实现要点def floyd(n, graph): # graph是邻接矩阵graph[i][j]表示i到j的直接距离无边为无穷大inf dist [[float(inf)] * n for _ in range(n)] for i in range(n): dist[i][i] 0 for j in range(n): if graph[i][j] ! float(inf): dist[i][j] graph[i][j] # 核心三重循环 for k in range(n): for i in range(n): for j in range(n): if dist[i][k] ! float(inf) and dist[k][j] ! float(inf): dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]) return dist注意Floyd算法的时间复杂度是O(n^3)因此只适用于节点数不多通常n500的稠密图。在数学建模中如果问题规模较大通常需要结合问题特性如网络流、Dijkstra算法等来求解不能盲目套用Floyd。此外Floyd算法可以处理负权边但不能处理负权环环上总权值为负否则最短路径无定义。4. 数学建模实战从赛题到动态规划模型掌握了经典模型我们来看如何将其应用到真实的数学建模问题中。我以两个典型的赛题方向为例拆解建模思路。4.1 场景一生产库存与资源调度问题这类问题在国赛、美赛中非常常见例如2021年国赛C题“生产企业原材料的订购与运输”就涉及多阶段的采购与库存决策。其核心是在满足需求约束下平衡采购/生产成本与库存成本实现总成本最小化。建模步骤细化阶段划分通常以时间周、月为阶段。假设共有T个时期。状态定义最常见的状态是每个时期初的库存水平I_t。有时如果存在价格波动、产能调整等情况状态可能需要扩展例如包含“当前是否处于设备维护期”、“当前原材料价格区间”等。决策变量每个时期的生产量/采购量X_t。状态转移I_{t1} I_t X_t - D_t其中D_t为t时期的需求。成本函数与递推方程阶段成本C_t(I_t, X_t) pc_t * X_t hc_t * I_t。其中pc_t是单位生产/采购成本可能随时间或采购量变化hc_t是单位库存持有成本。可能包含固定成本如果生产会产生一个固定设置成本S_t这会将问题引入“批量问题”模型增加决策的复杂性。递推方程逆序F_t(I_t) min_{X_t} { C_t(I_t, X_t) F_{t1}(I_t X_t - D_t) }满足0 X_t MaxProduction,I_t X_t D_t(满足需求)I_{t1} 0(库存非负)。边界条件F_{T1}(I_{T1}) v * I_{T1}。其中v是期末库存的单位残值可能为0。或者规定期末必须无库存则I_{T1}0为固定边界。编程求解技巧离散化库存I_t和生产量X_t通常是连续变量。为了用动态规划求解必须进行离散化。例如根据历史数据和产能确定库存水平的可能范围[0, I_max]然后以某个步长如1, 10, 100进行离散。生产量X_t也同样处理。离散的粒度需要在计算精度和计算时间之间权衡。状态空间枚举对于每个阶段t枚举所有可能的状态I_t离散值。对于每个状态枚举所有可行的决策X_t离散值计算成本并找到使总成本最小的决策记录下F_t(I_t)和对应的最优决策X_t^*(I_t)。回溯找最优策略从第一阶段开始根据初始库存I_1找到最优决策X_1^*然后根据状态转移方程算出I_2再查表找到I_2下的最优决策X_2^*以此类推直到最后一个阶段。避坑指南离散化步长的选择至关重要。步长太大结果不精确可能错过最优解步长太小状态空间爆炸计算时间无法承受。一个实用的技巧是先用较大的步长快速计算一个粗略解然后在粗略解附近缩小范围用更小的步长进行精细搜索。此外如果成本函数或约束条件非线性程度很高可能需要结合其他优化方法如非线性规划来求解每个子问题动态规划只负责处理阶段间的递推。4.2 场景二投资组合与路径规划问题这类问题强调在风险或约束下的多阶段决策优化。例如2020年美赛D题“与珊瑚共生”中涉及无人机在多个点之间进行数据收集的路径规划可以抽象为带时间窗和资源约束的最短路径问题。以多阶段投资问题为例假设有M种资产计划投资N个时期。初始资金为S0。每个时期你可以调整资产配置。已知每种资产在每个时期的收益率随机变量但这里我们先考虑确定性情况和风险。目标是N期后期望财富最大同时控制风险。建模思路阶段划分每个投资时期为一个阶段共N个阶段。状态定义状态是每个时期初的资产组合情况。一个最简化的模型是状态只定义为当前持有的总财富W_t。更复杂的模型状态需要是一个M维向量表示每种资产持有的金额。决策变量决策是资产配置比例向量u_t (u_{t1}, ..., u_{tM})其中u_{ti}是投资于资产i的比例满足sum u_{ti} 1。状态转移W_{t1} W_t * sum_{i1}^{M} [u_{ti} * (1 r_{ti})]其中r_{ti}是资产i在时期t的收益率。指标函数最终目标是最大化期末财富W_N。但通常也会在过程中考虑风险。一种常见方法是使用均值-方差模型将风险方差作为惩罚项加入目标函数或者作为约束条件。递推方程V_t(W_t) max_{u_t} { E[ V_{t1}(W_{t1}) ] }其中E表示期望。如果考虑风险目标函数会变成max E[W_N] - λ * Var(W_N)这会使问题复杂化通常需要利用二次规划或随机动态规划来求解。在路径规划中的应用变体 对于无人机数据收集问题阶段是访问节点的顺序。状态可以定义为(当前节点 已收集的数据量 剩余电量/时间)。决策是下一个访问哪个节点。状态转移由移动距离耗电/耗时和数据收集量决定。指标函数是最小化总时间或总能耗或者最大化收集的数据量。这通常是一个带资源约束的最短路径问题可以用动态规划求解但状态空间会随着节点数增加而指数级增长组合爆炸。实操心得对于状态空间巨大的问题如节点数多的路径规划直接动态规划是不可行的。此时需要结合启发式算法如遗传算法、模拟退火或近似动态规划方法。在数学建模论文中如果采用动态规划框架必须清晰说明状态的定义、决策空间、转移方程和目标函数。即使因为计算复杂而采用了启发式求解动态规划模型作为问题的精确描述和理论基准仍然具有重要价值。你可以用动态规划求解小规模实例来验证启发式算法的有效性。5. 编程实现核心技巧与调试策略理论模型建立后编程实现是另一大挑战。动态规划的代码看似简单但调试起来往往令人头疼。5.1 自顶向下与自底向上这是两种基本的实现方式。自底向上递推这是我们最常用的方法。从最小的子问题开始逐步计算更大的子问题直到解决原问题。通常使用数组DP表来存储子问题的解。优点是效率高易于理解缺点是有时需要计算所有子问题即使有些子问题对最终解没有贡献。# 斐波那契数列 - 自底向上 def fib_bottom_up(n): if n 1: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]自顶向下记忆化搜索从原问题出发试图递归地解决它。如果遇到一个子问题已经解决过就直接返回存储的结果记忆否则计算它并存储。这本质上是递归缓存。优点是只计算必要的子问题代码更贴近原始的递归关系缺点是递归有栈溢出风险常数开销可能略大。# 斐波那契数列 - 自顶向下记忆化搜索 memo {} def fib_top_down(n): if n 1: return n if n not in memo: memo[n] fib_top_down(n-1) fib_top_down(n-2) return memo[n]选择建议在数学建模中如果问题规模明确且状态空间可以完整遍历推荐使用自底向上的递推逻辑清晰便于调试和输出中间结果。如果状态空间巨大但稀疏很多状态不会被访问或者递归关系非常直观但难以用循环表示可以考虑自顶向下的记忆化搜索。5.2 边界条件与初始化这是动态规划代码中最容易出错的部分之一。边界条件处理不好整个递推就会像多米诺骨牌一样倒塌。常见边界情况索引越界在访问dp[i-1],dp[i-w]时必须确保i-1 0,i-w 0。在编程时通常将DP数组大小设为n1或V1并从索引1开始使用索引0作为边界。初始状态赋值dp[0]或dp[0][...]通常代表“空”或“初始”状态需要根据问题语义仔细赋值。例如背包问题中dp[0][j]表示考虑0件物品无论背包容量j多大最大价值都是0。所以dp[0][0...V] 0。在路径问题中dp[0][start] 0表示从起点到起点距离为0到其他点距离为无穷大。非法状态处理有些状态在物理意义上是不存在的。例如在生产计划中库存不能为负。在递推时如果某个决策导致了负库存这个决策就是非法的其对应的成本应该设为无穷大float(inf)这样在取最小值时它就不会被选中。调试策略打印DP表对于二维DP在循环中打印出关键的DP表内容是调试最有效的方法。观察每个dp[i][j]的值是否符合你的预期。小规模测试先用一个非常小的、你手工能算出结果的例子来测试代码。比如背包问题用2个物品容量为5手动计算最优解然后看程序输出是否一致。对比暴力枚举对于小规模问题n20可以写一个暴力枚举所有可能解的程序与你的动态规划结果对比。这是验证DP算法正确性的“金标准”。5.3 空间优化与时间优化当问题规模很大时优化至关重要。空间优化主要利用滚动数组。如果递推方程中当前状态dp[i][...]只依赖于上一行dp[i-1][...]那么就可以将二维数组压缩成一维数组通过逆序或正序更新来保证状态依赖的正确性如前文背包问题所示。时间优化动态规划的时间复杂度通常是O(状态数 * 决策数)。优化方向包括减少状态数重新设计状态定义合并等价状态。减少决策数对于每个状态并非所有决策都需要枚举。例如在完全背包问题中如果物品价值低体积大显然不是好选择。但更通用的优化是单调队列优化或斜率优化这些常用于特定的DP方程形式如形如dp[i] min{ dp[j] cost(j, i) }可以将在某些情况下将决策枚举从O(n)降到O(1)或O(logn)。在数学建模中如果时间紧迫可以优先考虑能否重新建模来简化状态转移其次再考虑这些高级优化技巧。6. 论文写作要点与常见误区在数学建模论文中如何清晰地呈现你的动态规划模型直接影响评委的理解和评分。6.1 模型表述规范符号说明表必须要有清晰列出所有阶段、状态变量、决策变量、参数如成本、需求的符号、含义和单位。这是论文的“字典”。模型假设明确列出你的模型基于哪些假设。例如“假设每个阶段的需求是确定已知的”、“假设库存成本是线性的”、“不考虑缺货情况”等。合理的假设能简化问题突出核心矛盾。递推方程这是模型的核心。要用规范的数学公式写出状态转移方程和指标函数的递推关系。建议使用“定义-方程”的格式。示例定义最优值函数F_t(I)为从第t阶段开始初始库存为I采用最优策略到期末的最小总成本。递推方程F_t(I) min_{0≤X≤X_max} { C_t * X h * I F_{t1}(I X - D_t) } 其中I X ≥ D_t。边界条件F_{T1}(I) s * Is为期末残值率。算法流程图对于复杂的动态规划算法尤其是包含了离散化、回溯等步骤画一个清晰的流程图能让评委快速把握你的求解思路。流程图应包括初始化、阶段循环、状态枚举、决策枚举、更新DP表、回溯最优解等关键步骤。6.2 结果分析与可视化最优策略表输出最终得到的最优策略。例如对于生产计划问题给出每个阶段在不同初始库存下的最优生产量。这通常是一个二维表格。敏感性分析这是加分项。分析关键参数如需求波动、成本变化对最优总成本和最优策略的影响。例如“当单位生产成本上涨10%时总成本增加约8%且最优策略倾向于减少单次生产批量增加生产次数以降低库存成本。” 这体现了你对模型鲁棒性的思考。可视化将结果用图表展示。折线图展示各阶段的最优生产量/库存量变化趋势。热力图如果状态是二维的如库存和另一状态可以用热力图展示最优值函数或最优决策在不同状态组合下的分布。对比图将动态规划的结果与其他简单策略如恒定生产策略、按需生产策略进行对比突出动态规划的优势。6.3 常见误区与改进建议误区一混淆阶段与状态。阶段是时间或步骤的划分状态是阶段点的“情况描述”。一个阶段可以有多个状态。误区二状态定义不满足无后效性。这是最致命的错误。务必检查一旦当前状态确定后续决策是否与之前的历史独立如果还需要知道之前的具体路径状态定义就需要扩充。误区三离散化过于粗糙或精细。过于粗糙导致结果不准过于精细导致“维数灾难”程序跑不完。需要在论文中说明你选择离散化步长的依据例如“根据历史数据库存水平通常在0-1000单位之间波动我们以50单位为步长进行离散在保证计算精度的前提下将状态数控制在20个以内。”误区四只给结果没有分析。论文不是代码实验报告。必须对结果进行解释为什么最优策略呈现出这样的规律它符合经济直觉吗参数变化时策略如何响应这体现了你对问题的深入理解。改进建议考虑随机性。很多赛题的需求、价格等参数是随机的。这时确定性动态规划就不够了。可以引入随机动态规划或近似动态规划。例如假设需求服从某个概率分布那么状态转移方程中的下一阶段状态就不是确定的而是期望值。此时最优值函数F_t(I)的定义变为“期望总成本”递推方程中需要加入求期望的运算。这大大增加了复杂度但模型也更贴近现实。如果时间允许尝试向这个方向拓展会是论文的一大亮点。动态规划的精髓在于“以空间换时间”和“最优决策的嵌套结构”。它要求建模者具备将复杂问题分解并抽象的能力。在数学建模竞赛中不要奢望用一个动态规划模型解决所有问题但它绝对是你在处理序列决策、资源分配、路径优化这类问题时的首选工具之一。多练习经典模型理解其思想本质在遇到新问题时你才能灵活地将它“匹配”和“改造”到你的模型框架中。最后一定要动手编程实现调试过程中遇到的坑会让你对模型的理解深刻十倍。
