数学建模备赛动态规划一定是绕不开的一类方法。我接触数学建模这几年无论是国赛、华为杯还是校内的模拟赛凡是要在有限资源下做“最优决策”的题目动态规划都可能是最快出结果的方案——而且它不需要外挂任何工具箱用MATLAB原生代码就能跑。这篇文章我从真正建模的角度把动态规划的分拆思路、建模套路、三组可以直接抄的MATLAB例题代码以及我踩过的坑一次讲清楚适合正在备赛或刚接触动态规划的同学对照着练习。我写这类文章的习惯是先讲清楚“这东西到底在干嘛”再上代码。因为数学建模比赛里代码只是最后落地的一步真正的分数差距在于你能不能把问题抽象成动态规划模型。所以前面几节会比较偏思路后面全部是能直接运行的MATLAB代码。1. 动态规划到底在解决什么问题1.1 我在数学建模里最常用它的场景数学建模题目里有相当一部分可以归成“多阶段决策问题”。什么叫多阶段决策就是整个问题不是一步到位的而是要一步一步地做决定每一步都会影响后续的结果。比如路径规划里你要决定先走哪条路、再走哪条路资源分配里你要决定先给哪个项目投钱、再给哪个项目投钱库存决策里你要决定每个月生产多少、留多少库存。这些场景里当前这一步的收益和代价会把后面的状态一起拖进来没法单独拿出来“贪心”地解。动态规划最聪明的地方在于它把“已经算过的子问题结果”记在一张表里后面用到的时候直接查表而不是重新计算一遍。这个思路很像记账你不需要每次花钱的时候把钱包里的钱全部重新数一遍你只要记住上一次的余额每次只更新这次的支出和收入就行。我经常跟队员说动态规划就是一个“自动记账的最优决策器”它帮你把每个状态下的最优值都记下来最后从表里找到最终答案。这里也顺便说一句动态规划并不神秘它不是什么高深的数学理论而更像一种“聪明的穷举”——把所有可能的决策都枚举一遍但通过记录中间结果把复杂度从指数级压到多项式级。理解这一点你就知道动态规划能处理的数据规模大概是几位数了一般二维状态表能开到几百乘几百三维就要谨慎一些。1.2 两个关键性质最优子结构与重叠子问题用动态规划的前提是题目具备两个性质。第一个叫最优子结构。意思是如果整个问题的最优解里包含了某个子问题那么这个子问题的解也一定是最优的。我常打一个比方假如从A城到C城的路线必须先经过B城那么从A到B这一段也一定是最短路径否则就能用一条更短的从A到B的路替换得到一条更短的A到C路线这就矛盾了。建模的时候你只要发现“最后一步做了某个决策剩下的部分变成了一个规模更小的同类问题”基本就可以往最优子结构上靠。第二个叫重叠子问题。意思是不同的决策路径会反复遇到同一个子问题。最典型的例子是斐波那契数列计算f(5)的时候会算f(4)和f(3)计算f(4)的时候又会算f(3)和f(2)f(3)被重复算了多次。如果没有重叠子问题那动态规划的表就白建了因为反正每个状态只算一次。所以拿到题目先别急着写转移方程先问自己如果把问题拆小子问题的结果会被多次用到吗如果会动态规划就适合如果每个子问题都只出现一次那可能直接用递归或搜索就行。1.3 状态、转移、边界动态规划的三板斧所有动态规划题翻来覆去就是三件事定义状态、写转移方程、定边界条件。状态就是你那张表里每个格子的含义。比如“最少硬币问题”里dp(i)可以定义为“凑出金额i需要的最少硬币数”。状态定义是整个动态规划的灵魂定义得好转移方程水到渠成定义得不好后面怎么写都别扭。我的经验是状态通常由题目里的“约束条件”和“求解目标”共同决定。题目说背包容量是W那状态里就要有容量这一维题目说物品有n个那状态里就要有物品数量这一维。转移方程描述的是“当前状态怎么由更小的状态推出来”。这一步的技巧是倒着想假设我已经到了最后一步最后一步做了什么决策比如凑出金额11最后一步可能是取了一枚1元、3元或5元硬币那么之前的状态就是凑出10、8或6元。用这种方式倒推转移方程基本不会写错。边界条件就是表的第一行、第一列怎么填。比如凑出金额0需要0枚硬币背包容量0时价值是0这些都是起点。边界条件错了整个表就算错了。我见过很多同学转移方程写得漂亮结果初始化少了一个格子整道题废掉。2. 拿到一道题怎么判断该不该用动态规划2.1 题面里的四个典型信号比赛时间紧张不可能每个题目都深入试一遍。我总结出四个快速判断信号符合两个以上基本可以优先考虑动态规划。第一题目求的是“最大值”“最小值”“最少步数”“最优方案数”这类词。这些是动态规划的典型目标。第二题目有明显的“多阶段”特征也就是决策是一步一步做的而且后面一步依赖前面一步的结果比如“前i个”“前k个月”“前n个项目”这种描述。第三把题目里的数据规模缩小之后子问题和原问题是同构的也就是“规模更小的同一个问题”。第四如果直接暴力枚举会发现大量重复计算指数级复杂度完全跑不动。我说一个反面例子帮大家加深印象如果一道题只是单纯求“所有点之间的最短路径”而且没有阶段可分那更适合用Floyd或者多次Dijkstra而不是动态规划。动态规划不是万能的它擅长的是“有明确阶段、有状态依赖”的问题。2.2 四步建模法遇到新题不慌张我建模的时候习惯按四步走定状态、写方程、设边界、定顺序。第一步定状态。状态里通常包含两个东西——你处理到哪个阶段了以及当前的核心约束值。比如背包问题是“前i个物品”和“当前容量j”资金分配问题是“前k个项目”和“已分配资金m”。这里的阶段就是循环里的外层变量。第二步写转移方程。逻辑是“枚举最后一步的所有可能取最优”。这里有个小技巧如果转移方程写不出来就多写几项递推比如dp(i)依赖dp(i-1)、dp(i-3)、dp(i-5)写出来再看规律。第三步设边界。一般把“什么都没处理”的状态设成0或者无穷大具体是哪个取决于你求的是最大还是最小。第四步定顺序。动态规划必须保证计算一个状态时它依赖的所有状态都已经算过了。大多数问题是从小到大递推但也有一些特殊问题需要调整顺序比如背包问题里的一维滚动数组就要注意内层循环倒着写。这个四步法应对大多数数学建模里的常规动态规划题都够用。我之前辅导过几支队伍很多人卡在第一步状态定义上就是因为没想清楚“题目问什么就把什么塞进状态里”。记住这句话状态定义会顺畅很多。3. 例题实战一最少硬币问题3.1 问题描述与状态定义先来一道最经典的入门题。假设硬币只有1元、3元、5元三种面值每种面值数量无限现在要凑出11元问最少用几枚硬币。这道题符合动态规划的所有特征目标是最小值决策是一枚一枚选硬币而且每个子问题“凑出金额i”和原问题结构完全一致。状态定义很简单dp(i)表示凑出金额i需要的最少硬币数。初始化dp(0)0因为凑0元不用硬币。转移方程的核心思路是倒推最后一步如果最后一步用了一枚面值为c的硬币那之前的金额就是i-c需要的硬币数是dp(i-c)1。因为硬币有三种面值所以取三种情况的最小值写成数学形式就是dp(i) min(dp(i-1)1, dp(i-3)1, dp(i-5)1)这个公式看起来朴素但它背后就是最优子结构凑出i元的最优解里去掉最后一枚硬币后剩下的i-c元也一定是最优的。重叠子问题也很明显凑11会用到凑10、凑8、凑6的结果而计算凑10时又会用到凑9、凑7、凑5……大量子问题被反复使用。3.2 MATLAB代码实现与运行结果在MATLAB里写这段代码最容易踩的坑是下标从1开始。我的做法是让dp(1)对应金额0dp(2)对应金额1以此类推这样写循环时逻辑清楚不会乱。%% 最少硬币问题 % 硬币面值 1、3、5数量无限凑出 11 元最少需要几枚硬币 % dp(i) 表示凑出金额 i-1 需要的最少硬币数MATLAB下标从1开始 coins [1, 3, 5]; amount 11; INF 1e9; % 用一个足够大的数表示“凑不出来” dp zeros(1, amount 1); % dp(1) 对应金额 0 dp(1) 0; % 凑出 0 元需要 0 枚硬币 for i 2 : amount 1 cur i - 1; % 当前要凑的金额 dp(i) INF; % 先假设凑不出来 for c coins if c cur dp(i - c 1) 1 dp(i) dp(i) dp(i - c 1) 1; end end end fprintf(凑出 %d 元最少需要 %d 枚硬币\n, amount, dp(amount 1));运行结果输出凑出11元最少需要3枚硬币。真实方案是551或者533都是3枚。你可以自己手算验证一下dp(1)1dp(3)1dp(5)1dp(6)2dp(8)2dp(10)2dp(11)3。思路完全对得上。这道题虽然简单但它把动态规划“查表替代重复计算”的威力体现得很清楚如果不查表用递归去算状态会指数爆炸查表之后只需要算11个状态。4. 例题实战二01背包问题4.1 背包问题为什么是数学建模的常客背包问题几乎是所有动态规划教材的必备例题也是数学建模竞赛里的“常客”因为它抽象了一大批实际问题有n件物品每件有重量w(i)和价值v(i)背包容量是W每件物品要么拿要么不拿问怎么装能让总价值最大。为什么说它是“常客”因为很多调度、装载、投资问题都可以改造成背包模型。比如某次比赛要选择做哪几道题每道题花的时间不同、拿的分不同总时间有限这就是背包问题。再比如物流里选哪几个货物装车也是背包问题。所以别小看它学会背包问题的建模方法等于学会了一整类问题。状态定义是二维的dp(i, j)表示考虑前i个物品、背包容量为j时能获得的最大价值。这里有两个维度因为物品编号和剩余容量共同决定一个子问题。转移方程也用“最后一步”来想第i个物品要么不拿那价值等于dp(i-1, j)要么拿那需要先腾出w(i)的空间价值等于dp(i-1, j-w(i)) v(i)。两者取较大值。4.2 MATLAB实现二维状态表与方案回溯我用一个具体的例子来写代码。假设有5个物品重量和价值分别是物品1(2,3)、物品2(3,4)、物品3(4,5)、物品4(5,8)、物品5(9,10)背包容量10求最大价值。%% 01背包问题 % 5 个物品背包容量 10求能装入的最大总价值 % dp(i, j) 表示考虑前 i-1 个物品、容量为 j-1 时的最大价值下标从1开始 w [2, 3, 4, 5, 9]; v [3, 4, 5, 8, 10]; W 10; n length(w); dp zeros(n 1, W 1); % 第1行表示0个物品第1列表示容量0 for i 2 : n 1 wi w(i - 1); vi v(i - 1); for j 1 : W 1 cap j - 1; % 当前容量因为下标从1开始 dp(i, j) dp(i - 1, j); % 不拿第 i-1 个物品 if cap wi cand dp(i - 1, cap - wi 1) vi; if cand dp(i, j) dp(i, j) cand; % 决定拿第 i-1 个物品 end end end end fprintf(最大总价值 %d\n, dp(n 1, W 1));运行结果输出最大总价值 15。对应方案是选物品1、物品2和物品4总重量23510总价值34815。代码里最关键的一行是dp(i, j) dp(i - 1, j)很多同学会漏掉这个“不拿”的继承关系。如果漏了后续比较就会出现负数或错误的结果。如果想进一步输出到底装了哪些物品可以在算完表之后做一次“回溯”。回溯的思路是从表的右下角往左上角走如果dp(i, j)和dp(i-1, j)不相等说明第i-1个物品一定被拿走了于是跳到dp(i-1, j-w(i-1))如果相等说明该物品没拿直接跳到上一行。%% 回溯找出被选中的物品 x zeros(1, n); i n 1; j W 1; while i 1 if dp(i, j) ~ dp(i - 1, j) x(i - 1) 1; % 第 i-1 个物品被选 j j - w(i - 1); % 减少对应容量 end i i - 1; end disp(x); % 非 0 的位置表示被选中的物品运行这段x会显示为[1 1 0 1 0]正好对应物品1、2、4。需要提醒的是如果存在多个最优方案回溯只会得到其中一个因为dp表只记录了数值没有记录决策路径。5. 例题实战三资金分配问题5.1 从背包到多阶段资源分配的思路升级第三道例题我特意选了一个更贴近数学建模实战的“资金分配问题”因为比赛里经常出现类似的资源调度、投资组合题。题面是这样的某公司有8万元资金计划投到A、B、C三个项目中每个项目的投资额只能是0、2、4、6、8万元各项目在不同投资额下的收益如下表投资额(万元)项目A收益项目B收益项目C收益00002324465669888121110问应该给每个项目分配多少钱才能使总收益最大。这个问题比背包问题多了一个维度上的升级背包里每件物品只有拿或不拿两种状态而资金分配里每个项目可以选择多种投资额。但底层逻辑还是一样它也是一个多阶段决策问题决策顺序是“先看A项目怎么分再看B项目怎么分最后看C项目怎么分”。所以状态定义可以沿用背包的思路dp(k, m)表示把m万元分配给前k个项目时能获得的最大收益。转移方程是dp(k, m) max( 当前第k个项目分配x万元 dp(k-1, m-x) )其中x必须在允许的投资额档位里并且x不能超过m。这里要枚举x的所有可能取值取最大值。你可以理解为背包问题里“最后一步是决定第i个物品拿不拿”而这里“最后一步是决定第k个项目分多少钱”。5.2 MATLAB实现多阶段递推与结果验证写代码之前先看数据怎么放。收益表用矩阵存行对应投资额档位列对应项目投资额档位单独存一个向量方便循环里用。%% 资金分配问题 % 8万元资金分给 A、B、C 三个项目投资额只能取 0、2、4、6、8 万 % dp(k, m) 表示把 m 万元分配给前 k 个项目时的最大收益 amounts [0, 2, 4, 6, 8]; profit [ 0 0 0; 3 2 4; 6 5 6; 9 8 8; 12 11 10 ]; total 8; nProj 3; nLevel length(amounts); dp zeros(nProj 1, total 1); for k 2 : nProj 1 % 第 k 行对应前 k-1 个项目 for m 0 : total % 当前可分配资金 best 0; for idx 1 : nLevel % 枚举第 k-1 个项目投多少钱 x amounts(idx); if x m cand profit(idx, k - 1) dp(k - 1, m - x 1); if cand best best cand; end end end dp(k, m 1) best; end end fprintf(最大总收益 %d 万元\n, dp(nProj 1, total 1));运行结果输出最大总收益 13万元。对应方案是A项目投6万元得9万元收益C项目投2万元得4万元收益B项目不投总收益13万元。你可以手动验一遍表A投6、B投0、C投2或者A投8、C投0后者只拿12确实13最大。这也说明动态规划不会漏掉组合里那些“看似不平均”的分配方案。如果要追查最优分配方案思路和背包回溯一样从dp(4, 9)往回看检查是哪个x让dp(4, 81)达到最大值然后递归往下查。比赛里如果只需要最优值那直接读dp表的右下角就够了如果题目要求给出方案再加回溯部分。6. 我踩过的坑和调试心得6.1 MATLAB下标偏移最容易翻车的细节写MATLAB动态规划最高频的报错绝对是“索引超出数组边界”。原因是MATLAB的下标从1开始而动态规划的公式通常是从0开始的。比如币值问题里“金额0”对应的其实是dp(1)金额11对应dp(12)。我见过太多人在循环里写成dp(i - c) 1结果第一次循环就报错或者干脆算出一张全错的表。我的解决办法是统一约定所有和“金额/容量”有关的状态都让下标加1。也就是状态变量为i时实际金额是i-1。写代码时在循环最前面加一行注释比如“dp(1)对应金额0”防止自己写着写着忘了。变量取名也尽量用cur、cap这类能提醒自己的名字不要直接拿i去和硬币面值做减法。还有一个小技巧是先在纸上画出dp表的结构标好第一行、第一列分别代表什么再写代码。这个习惯看起来笨但能省下大量调试时间。6.2 初始化与边界条件的取舍初始化是另一大坑。求最小值的问题比如最少硬币通常初始化为一个很大的数我用INF 1e9表示“暂未找到方案”。这里有个细节别用inf因为后面判断里如果出现inf 1计算结果可能变成inf虽然大多时候不会出错但1e9这种大数更直观、更好调试。求最大值的问题比如背包和资金分配我更喜欢把dp表整体初始化为0因为“不选任何东西”的收益天然是0。不过要小心如果物品重量可能为0或者存在负收益这种初始化就要重新考虑了。比赛里只有极少数情况会出现负收益但一旦遇到0初始化就会把负值全部吞掉所以拿到题目先看数据取值范围别上来就抄模板。另外涉及金额或容量时我建议全部用整数计算。浮点数在比较“是否相等”时很容易出问题动态规划里频繁用比较运算符一旦出现0.10.2不等于0.3这种经典浮点误差排错会让你怀疑人生。真遇到小数先放大成整数算完再缩小。6.3 常见问题速查表我整理了一张调试速查表是我在实际写动态规划时最常遇到的问题遇到报错或结果不对先对照这张表排查。问题可能原因排查方法结果比预期小初始化用了0但求的是最小值检查状态定义是求最大还是最小把初值改成INF运行报数组越界状态下标和实际金额/容量偏移没对齐在循环顶部注释“下标1对应数值0”逐行打印核对输出全部是0转移方程里漏了“不选/不拿”的继承项背包问题先写dp(i,j)dp(i-1,j)再比较递归思路能算对循环版本乱计算顺序不对后面状态依赖了未算出的状态检查循环是否从小到大、外层是否阶段变量回溯结果和最优值对不上有多个最优方案回溯只按一种方式走确认回溯判断用不等号并且每跳一步都缩容运行速度很慢状态维数太高或循环里做了无效枚举先看数据范围三维以上考虑降维或换方法最后再分享一个小技巧动态规划代码写完先不要急着跑大数据拿题目的小规模样例手算一遍再用代码跑。我几乎所有动态规划的debug最后都发现问题不是代码实现而是状态定义或者边界条件一开始就没想清楚。手算三五个状态就足够暴露问题。三道例题的代码我都放在上面的小节里可以直接复制运行。建议你每道题都改一改参数比如把最少硬币的面值换成[2, 3, 7]背包容量的数字加大或者把资金分配的收益表换成自己编的数据看看dp表的变化规律。真正把状态转移方程“背下来”是没用的能熟练地针对新题改出状态和转移方程才算掌握了动态规划。
数学建模必会：动态规划原理、MATLAB实现与实战例题详解
数学建模备赛动态规划一定是绕不开的一类方法。我接触数学建模这几年无论是国赛、华为杯还是校内的模拟赛凡是要在有限资源下做“最优决策”的题目动态规划都可能是最快出结果的方案——而且它不需要外挂任何工具箱用MATLAB原生代码就能跑。这篇文章我从真正建模的角度把动态规划的分拆思路、建模套路、三组可以直接抄的MATLAB例题代码以及我踩过的坑一次讲清楚适合正在备赛或刚接触动态规划的同学对照着练习。我写这类文章的习惯是先讲清楚“这东西到底在干嘛”再上代码。因为数学建模比赛里代码只是最后落地的一步真正的分数差距在于你能不能把问题抽象成动态规划模型。所以前面几节会比较偏思路后面全部是能直接运行的MATLAB代码。1. 动态规划到底在解决什么问题1.1 我在数学建模里最常用它的场景数学建模题目里有相当一部分可以归成“多阶段决策问题”。什么叫多阶段决策就是整个问题不是一步到位的而是要一步一步地做决定每一步都会影响后续的结果。比如路径规划里你要决定先走哪条路、再走哪条路资源分配里你要决定先给哪个项目投钱、再给哪个项目投钱库存决策里你要决定每个月生产多少、留多少库存。这些场景里当前这一步的收益和代价会把后面的状态一起拖进来没法单独拿出来“贪心”地解。动态规划最聪明的地方在于它把“已经算过的子问题结果”记在一张表里后面用到的时候直接查表而不是重新计算一遍。这个思路很像记账你不需要每次花钱的时候把钱包里的钱全部重新数一遍你只要记住上一次的余额每次只更新这次的支出和收入就行。我经常跟队员说动态规划就是一个“自动记账的最优决策器”它帮你把每个状态下的最优值都记下来最后从表里找到最终答案。这里也顺便说一句动态规划并不神秘它不是什么高深的数学理论而更像一种“聪明的穷举”——把所有可能的决策都枚举一遍但通过记录中间结果把复杂度从指数级压到多项式级。理解这一点你就知道动态规划能处理的数据规模大概是几位数了一般二维状态表能开到几百乘几百三维就要谨慎一些。1.2 两个关键性质最优子结构与重叠子问题用动态规划的前提是题目具备两个性质。第一个叫最优子结构。意思是如果整个问题的最优解里包含了某个子问题那么这个子问题的解也一定是最优的。我常打一个比方假如从A城到C城的路线必须先经过B城那么从A到B这一段也一定是最短路径否则就能用一条更短的从A到B的路替换得到一条更短的A到C路线这就矛盾了。建模的时候你只要发现“最后一步做了某个决策剩下的部分变成了一个规模更小的同类问题”基本就可以往最优子结构上靠。第二个叫重叠子问题。意思是不同的决策路径会反复遇到同一个子问题。最典型的例子是斐波那契数列计算f(5)的时候会算f(4)和f(3)计算f(4)的时候又会算f(3)和f(2)f(3)被重复算了多次。如果没有重叠子问题那动态规划的表就白建了因为反正每个状态只算一次。所以拿到题目先别急着写转移方程先问自己如果把问题拆小子问题的结果会被多次用到吗如果会动态规划就适合如果每个子问题都只出现一次那可能直接用递归或搜索就行。1.3 状态、转移、边界动态规划的三板斧所有动态规划题翻来覆去就是三件事定义状态、写转移方程、定边界条件。状态就是你那张表里每个格子的含义。比如“最少硬币问题”里dp(i)可以定义为“凑出金额i需要的最少硬币数”。状态定义是整个动态规划的灵魂定义得好转移方程水到渠成定义得不好后面怎么写都别扭。我的经验是状态通常由题目里的“约束条件”和“求解目标”共同决定。题目说背包容量是W那状态里就要有容量这一维题目说物品有n个那状态里就要有物品数量这一维。转移方程描述的是“当前状态怎么由更小的状态推出来”。这一步的技巧是倒着想假设我已经到了最后一步最后一步做了什么决策比如凑出金额11最后一步可能是取了一枚1元、3元或5元硬币那么之前的状态就是凑出10、8或6元。用这种方式倒推转移方程基本不会写错。边界条件就是表的第一行、第一列怎么填。比如凑出金额0需要0枚硬币背包容量0时价值是0这些都是起点。边界条件错了整个表就算错了。我见过很多同学转移方程写得漂亮结果初始化少了一个格子整道题废掉。2. 拿到一道题怎么判断该不该用动态规划2.1 题面里的四个典型信号比赛时间紧张不可能每个题目都深入试一遍。我总结出四个快速判断信号符合两个以上基本可以优先考虑动态规划。第一题目求的是“最大值”“最小值”“最少步数”“最优方案数”这类词。这些是动态规划的典型目标。第二题目有明显的“多阶段”特征也就是决策是一步一步做的而且后面一步依赖前面一步的结果比如“前i个”“前k个月”“前n个项目”这种描述。第三把题目里的数据规模缩小之后子问题和原问题是同构的也就是“规模更小的同一个问题”。第四如果直接暴力枚举会发现大量重复计算指数级复杂度完全跑不动。我说一个反面例子帮大家加深印象如果一道题只是单纯求“所有点之间的最短路径”而且没有阶段可分那更适合用Floyd或者多次Dijkstra而不是动态规划。动态规划不是万能的它擅长的是“有明确阶段、有状态依赖”的问题。2.2 四步建模法遇到新题不慌张我建模的时候习惯按四步走定状态、写方程、设边界、定顺序。第一步定状态。状态里通常包含两个东西——你处理到哪个阶段了以及当前的核心约束值。比如背包问题是“前i个物品”和“当前容量j”资金分配问题是“前k个项目”和“已分配资金m”。这里的阶段就是循环里的外层变量。第二步写转移方程。逻辑是“枚举最后一步的所有可能取最优”。这里有个小技巧如果转移方程写不出来就多写几项递推比如dp(i)依赖dp(i-1)、dp(i-3)、dp(i-5)写出来再看规律。第三步设边界。一般把“什么都没处理”的状态设成0或者无穷大具体是哪个取决于你求的是最大还是最小。第四步定顺序。动态规划必须保证计算一个状态时它依赖的所有状态都已经算过了。大多数问题是从小到大递推但也有一些特殊问题需要调整顺序比如背包问题里的一维滚动数组就要注意内层循环倒着写。这个四步法应对大多数数学建模里的常规动态规划题都够用。我之前辅导过几支队伍很多人卡在第一步状态定义上就是因为没想清楚“题目问什么就把什么塞进状态里”。记住这句话状态定义会顺畅很多。3. 例题实战一最少硬币问题3.1 问题描述与状态定义先来一道最经典的入门题。假设硬币只有1元、3元、5元三种面值每种面值数量无限现在要凑出11元问最少用几枚硬币。这道题符合动态规划的所有特征目标是最小值决策是一枚一枚选硬币而且每个子问题“凑出金额i”和原问题结构完全一致。状态定义很简单dp(i)表示凑出金额i需要的最少硬币数。初始化dp(0)0因为凑0元不用硬币。转移方程的核心思路是倒推最后一步如果最后一步用了一枚面值为c的硬币那之前的金额就是i-c需要的硬币数是dp(i-c)1。因为硬币有三种面值所以取三种情况的最小值写成数学形式就是dp(i) min(dp(i-1)1, dp(i-3)1, dp(i-5)1)这个公式看起来朴素但它背后就是最优子结构凑出i元的最优解里去掉最后一枚硬币后剩下的i-c元也一定是最优的。重叠子问题也很明显凑11会用到凑10、凑8、凑6的结果而计算凑10时又会用到凑9、凑7、凑5……大量子问题被反复使用。3.2 MATLAB代码实现与运行结果在MATLAB里写这段代码最容易踩的坑是下标从1开始。我的做法是让dp(1)对应金额0dp(2)对应金额1以此类推这样写循环时逻辑清楚不会乱。%% 最少硬币问题 % 硬币面值 1、3、5数量无限凑出 11 元最少需要几枚硬币 % dp(i) 表示凑出金额 i-1 需要的最少硬币数MATLAB下标从1开始 coins [1, 3, 5]; amount 11; INF 1e9; % 用一个足够大的数表示“凑不出来” dp zeros(1, amount 1); % dp(1) 对应金额 0 dp(1) 0; % 凑出 0 元需要 0 枚硬币 for i 2 : amount 1 cur i - 1; % 当前要凑的金额 dp(i) INF; % 先假设凑不出来 for c coins if c cur dp(i - c 1) 1 dp(i) dp(i) dp(i - c 1) 1; end end end fprintf(凑出 %d 元最少需要 %d 枚硬币\n, amount, dp(amount 1));运行结果输出凑出11元最少需要3枚硬币。真实方案是551或者533都是3枚。你可以自己手算验证一下dp(1)1dp(3)1dp(5)1dp(6)2dp(8)2dp(10)2dp(11)3。思路完全对得上。这道题虽然简单但它把动态规划“查表替代重复计算”的威力体现得很清楚如果不查表用递归去算状态会指数爆炸查表之后只需要算11个状态。4. 例题实战二01背包问题4.1 背包问题为什么是数学建模的常客背包问题几乎是所有动态规划教材的必备例题也是数学建模竞赛里的“常客”因为它抽象了一大批实际问题有n件物品每件有重量w(i)和价值v(i)背包容量是W每件物品要么拿要么不拿问怎么装能让总价值最大。为什么说它是“常客”因为很多调度、装载、投资问题都可以改造成背包模型。比如某次比赛要选择做哪几道题每道题花的时间不同、拿的分不同总时间有限这就是背包问题。再比如物流里选哪几个货物装车也是背包问题。所以别小看它学会背包问题的建模方法等于学会了一整类问题。状态定义是二维的dp(i, j)表示考虑前i个物品、背包容量为j时能获得的最大价值。这里有两个维度因为物品编号和剩余容量共同决定一个子问题。转移方程也用“最后一步”来想第i个物品要么不拿那价值等于dp(i-1, j)要么拿那需要先腾出w(i)的空间价值等于dp(i-1, j-w(i)) v(i)。两者取较大值。4.2 MATLAB实现二维状态表与方案回溯我用一个具体的例子来写代码。假设有5个物品重量和价值分别是物品1(2,3)、物品2(3,4)、物品3(4,5)、物品4(5,8)、物品5(9,10)背包容量10求最大价值。%% 01背包问题 % 5 个物品背包容量 10求能装入的最大总价值 % dp(i, j) 表示考虑前 i-1 个物品、容量为 j-1 时的最大价值下标从1开始 w [2, 3, 4, 5, 9]; v [3, 4, 5, 8, 10]; W 10; n length(w); dp zeros(n 1, W 1); % 第1行表示0个物品第1列表示容量0 for i 2 : n 1 wi w(i - 1); vi v(i - 1); for j 1 : W 1 cap j - 1; % 当前容量因为下标从1开始 dp(i, j) dp(i - 1, j); % 不拿第 i-1 个物品 if cap wi cand dp(i - 1, cap - wi 1) vi; if cand dp(i, j) dp(i, j) cand; % 决定拿第 i-1 个物品 end end end end fprintf(最大总价值 %d\n, dp(n 1, W 1));运行结果输出最大总价值 15。对应方案是选物品1、物品2和物品4总重量23510总价值34815。代码里最关键的一行是dp(i, j) dp(i - 1, j)很多同学会漏掉这个“不拿”的继承关系。如果漏了后续比较就会出现负数或错误的结果。如果想进一步输出到底装了哪些物品可以在算完表之后做一次“回溯”。回溯的思路是从表的右下角往左上角走如果dp(i, j)和dp(i-1, j)不相等说明第i-1个物品一定被拿走了于是跳到dp(i-1, j-w(i-1))如果相等说明该物品没拿直接跳到上一行。%% 回溯找出被选中的物品 x zeros(1, n); i n 1; j W 1; while i 1 if dp(i, j) ~ dp(i - 1, j) x(i - 1) 1; % 第 i-1 个物品被选 j j - w(i - 1); % 减少对应容量 end i i - 1; end disp(x); % 非 0 的位置表示被选中的物品运行这段x会显示为[1 1 0 1 0]正好对应物品1、2、4。需要提醒的是如果存在多个最优方案回溯只会得到其中一个因为dp表只记录了数值没有记录决策路径。5. 例题实战三资金分配问题5.1 从背包到多阶段资源分配的思路升级第三道例题我特意选了一个更贴近数学建模实战的“资金分配问题”因为比赛里经常出现类似的资源调度、投资组合题。题面是这样的某公司有8万元资金计划投到A、B、C三个项目中每个项目的投资额只能是0、2、4、6、8万元各项目在不同投资额下的收益如下表投资额(万元)项目A收益项目B收益项目C收益00002324465669888121110问应该给每个项目分配多少钱才能使总收益最大。这个问题比背包问题多了一个维度上的升级背包里每件物品只有拿或不拿两种状态而资金分配里每个项目可以选择多种投资额。但底层逻辑还是一样它也是一个多阶段决策问题决策顺序是“先看A项目怎么分再看B项目怎么分最后看C项目怎么分”。所以状态定义可以沿用背包的思路dp(k, m)表示把m万元分配给前k个项目时能获得的最大收益。转移方程是dp(k, m) max( 当前第k个项目分配x万元 dp(k-1, m-x) )其中x必须在允许的投资额档位里并且x不能超过m。这里要枚举x的所有可能取值取最大值。你可以理解为背包问题里“最后一步是决定第i个物品拿不拿”而这里“最后一步是决定第k个项目分多少钱”。5.2 MATLAB实现多阶段递推与结果验证写代码之前先看数据怎么放。收益表用矩阵存行对应投资额档位列对应项目投资额档位单独存一个向量方便循环里用。%% 资金分配问题 % 8万元资金分给 A、B、C 三个项目投资额只能取 0、2、4、6、8 万 % dp(k, m) 表示把 m 万元分配给前 k 个项目时的最大收益 amounts [0, 2, 4, 6, 8]; profit [ 0 0 0; 3 2 4; 6 5 6; 9 8 8; 12 11 10 ]; total 8; nProj 3; nLevel length(amounts); dp zeros(nProj 1, total 1); for k 2 : nProj 1 % 第 k 行对应前 k-1 个项目 for m 0 : total % 当前可分配资金 best 0; for idx 1 : nLevel % 枚举第 k-1 个项目投多少钱 x amounts(idx); if x m cand profit(idx, k - 1) dp(k - 1, m - x 1); if cand best best cand; end end end dp(k, m 1) best; end end fprintf(最大总收益 %d 万元\n, dp(nProj 1, total 1));运行结果输出最大总收益 13万元。对应方案是A项目投6万元得9万元收益C项目投2万元得4万元收益B项目不投总收益13万元。你可以手动验一遍表A投6、B投0、C投2或者A投8、C投0后者只拿12确实13最大。这也说明动态规划不会漏掉组合里那些“看似不平均”的分配方案。如果要追查最优分配方案思路和背包回溯一样从dp(4, 9)往回看检查是哪个x让dp(4, 81)达到最大值然后递归往下查。比赛里如果只需要最优值那直接读dp表的右下角就够了如果题目要求给出方案再加回溯部分。6. 我踩过的坑和调试心得6.1 MATLAB下标偏移最容易翻车的细节写MATLAB动态规划最高频的报错绝对是“索引超出数组边界”。原因是MATLAB的下标从1开始而动态规划的公式通常是从0开始的。比如币值问题里“金额0”对应的其实是dp(1)金额11对应dp(12)。我见过太多人在循环里写成dp(i - c) 1结果第一次循环就报错或者干脆算出一张全错的表。我的解决办法是统一约定所有和“金额/容量”有关的状态都让下标加1。也就是状态变量为i时实际金额是i-1。写代码时在循环最前面加一行注释比如“dp(1)对应金额0”防止自己写着写着忘了。变量取名也尽量用cur、cap这类能提醒自己的名字不要直接拿i去和硬币面值做减法。还有一个小技巧是先在纸上画出dp表的结构标好第一行、第一列分别代表什么再写代码。这个习惯看起来笨但能省下大量调试时间。6.2 初始化与边界条件的取舍初始化是另一大坑。求最小值的问题比如最少硬币通常初始化为一个很大的数我用INF 1e9表示“暂未找到方案”。这里有个细节别用inf因为后面判断里如果出现inf 1计算结果可能变成inf虽然大多时候不会出错但1e9这种大数更直观、更好调试。求最大值的问题比如背包和资金分配我更喜欢把dp表整体初始化为0因为“不选任何东西”的收益天然是0。不过要小心如果物品重量可能为0或者存在负收益这种初始化就要重新考虑了。比赛里只有极少数情况会出现负收益但一旦遇到0初始化就会把负值全部吞掉所以拿到题目先看数据取值范围别上来就抄模板。另外涉及金额或容量时我建议全部用整数计算。浮点数在比较“是否相等”时很容易出问题动态规划里频繁用比较运算符一旦出现0.10.2不等于0.3这种经典浮点误差排错会让你怀疑人生。真遇到小数先放大成整数算完再缩小。6.3 常见问题速查表我整理了一张调试速查表是我在实际写动态规划时最常遇到的问题遇到报错或结果不对先对照这张表排查。问题可能原因排查方法结果比预期小初始化用了0但求的是最小值检查状态定义是求最大还是最小把初值改成INF运行报数组越界状态下标和实际金额/容量偏移没对齐在循环顶部注释“下标1对应数值0”逐行打印核对输出全部是0转移方程里漏了“不选/不拿”的继承项背包问题先写dp(i,j)dp(i-1,j)再比较递归思路能算对循环版本乱计算顺序不对后面状态依赖了未算出的状态检查循环是否从小到大、外层是否阶段变量回溯结果和最优值对不上有多个最优方案回溯只按一种方式走确认回溯判断用不等号并且每跳一步都缩容运行速度很慢状态维数太高或循环里做了无效枚举先看数据范围三维以上考虑降维或换方法最后再分享一个小技巧动态规划代码写完先不要急着跑大数据拿题目的小规模样例手算一遍再用代码跑。我几乎所有动态规划的debug最后都发现问题不是代码实现而是状态定义或者边界条件一开始就没想清楚。手算三五个状态就足够暴露问题。三道例题的代码我都放在上面的小节里可以直接复制运行。建议你每道题都改一改参数比如把最少硬币的面值换成[2, 3, 7]背包容量的数字加大或者把资金分配的收益表换成自己编的数据看看dp表的变化规律。真正把状态转移方程“背下来”是没用的能熟练地针对新题改出状态和转移方程才算掌握了动态规划。
