请教一下动态规划切割金属条的问题

xubokun1992

2016/9/12镜像同步6 回复

算法导论动态规划的第一节，切割金属条获得最大收益。我不理解的是最优化的表达式，按理说应该是先分割成两段，然后相加这两个子问题最优化的结果。（式15.1）可是为什么就可以等效成：第一段不用最优化，只对第二段算最优化？（式15.2）

订阅后，新回复会通过你的通知中心匿名送达。

6 条回复

yuyin100316机器人#1 · 2016/9/12

因为第一段已经最优化过了，你看公式15.2，第一段是pi，这个pi是计算过了的

iamluo机器人#2 · 2016/9/12

带备忘发自「贵邮」

xubokun1992机器人#3 · 2016/9/12

[ema27]我又看了看还是不明白。15.2中pi指的是图15-1中对应的原始价格，并没有优化过啊【在 yuyin100316 的大作中提到: 】 : 因为第一段已经最优化过了，你看公式15.2，第一段是pi，这个pi是计算过了的

yuyin100316机器人#4 · 2016/9/12

这个i是从n到1都有的，在i比较小的时候pi很可能是和ri一样的，不需要优化，剩下的部分是优化过的，在i比较打的时候基本上就不是最优的i值了，因为第一段应该由优化过的代替；举个栗子，8=5+2+1是最优，那么i取1时，r7应该是7=5+2的，而i=3时，原本应该是1+2的3没有被拆开所以3就不是最优的那个i。【在 xubokun1992 的大作中提到: 】 : 我又看了看还是不明白。15.2中pi指的是图15-1中对应的原始价格，并没有优化过啊

xubokun1992机器人#5 · 2016/9/12

蟹蟹，我大概明白了你的意思了。就是最终取得最优化的组合，pi的i总是比较小的数，此时pi=ri 【在 yuyin100316 的大作中提到: 】 : 这个i是从n到1都有的，在i比较小的时候pi很可能是和ri一样的，不需要优化，剩下的部分是优化过的，在i比较打的时候基本上就不是最优的i值了，因为第一段应该由优化过的代替； : 举个栗子，8=5+2+1是最优，那么i取1时，r7应该是7=5+2的，而i=3时，原本应该是1+2的3没有被拆开所以3就不是最优的那个i。

yuyin100316机器人#6 · 2016/9/13

对，不用谢的，我也是最近刚看【在 xubokun1992 的大作中提到: 】 : 蟹蟹，我大概明白了你的意思了。就是最终取得最优化的组合，pi的i总是比较小的数，此时pi=ri

请教一下 动态规划 切割金属条的问题

请教一下动态规划切割金属条的问题