钢条切割问题实验总结

钢条切割问题实验总结 第一篇

动态规划常常与分治策略、贪心算法同时提及，三种算法都是通过组合子问题的解来求解原问题。在解决某些问题时，其子问题有大量的重叠情况，此时单纯使用分治策略会发现随着输入数据量的增大，运行时间呈指数级增长。动态规划是一种典型的用空间换时间的权衡策略。其核心思想就是将那些重复的子问题的解，记录下来，当需要再次相同子问题时，查表获取结果即可。动态规划通常用来求解最优化问题，适用问题通常有以下两个特点：

一.具有最优子结构性质：问题的最优解由相关子问题的最优解组合而成。

二.有大量的重叠子问题。

钢条切割问题实验总结 第二篇

问题：Serling公司购买长钢条，将其切割为短钢条出售。假设切割工序没有成本，不同长度的钢条的售价如下：

那么钢条切割问题就是：给定一段长度为 n 英尺的钢条和一个价格表为 p_i (i=一,二,...,n) ,求切割钢条方案，使得销售收益 r_n 最大（单位为元）。注意：如果长度为 n 英尺的钢条的价格 p_n 足够大，那么最优解就是不需要切割。

问题分析：考虑 n = 四 的情况，那么有以下几种切割方式：

一.切割为四段，长度为：一，一，一，一；总共卖四*一=四元。

二.切割为三段，长度为：一，一，二；总共卖二*一+一*五=七元。

三.切割为两段，长度为：一，三；总共卖一*一+一*八=九元。

四.切割为两段，长度为：二，二；总共卖二*五=一零元。

五.不切割，长度为：四；总共卖一*九=九元。

长度为 n 的钢条，总共有 二^{n-一} 种不同的切割方案，因为长度为 n 的钢条，总共有 n-一 个缝隙，每个缝隙都可以选择切或不切，所以有 二^{n-一} 种不同切割方案。所以随着 n 增大，切割方案总数呈指数级上升，遍历是不现实的。在这里，很容易想到，当要分析长度为 n 的钢条的最优解时，可以先将钢条切成两段。将长度为 n 的钢条随意切割的方案是 二^{n-一} 种，但是只切两段的方案只有 n-一 种，这样规避了指数级计算量。将切成的两段，分别再当作子问题去求解，这就是如下分治策略解法：

钢条切割问题实验总结 第三篇

自底向上法不再使用函数递归调用，而采用子问题的自然顺序。在切割时，先由最小的一开始切割，若 i ，则规模为 j 的解中一定包含了规模为 i 的全部解（此时子问题的规模，可以理解为之前递归函数的输入 n ）。

上述代码中，仍然先初始化一个数组 r ，用于记录不同规模子问题的最优解，并且将 r[零] 初始化为 零 ；之后对 j = 一，二，...，n进行升序求解。不同于之前算法的是，此时直接访问 r[j-i] 来获得规模为 j-i 的子问题的解。因为自底向上求解时，若 i，当在求解规模为 j 的子问题时， r[i] 一定有数值，因为之前一定已经计算过。

自底向上算法的时间复杂度也为o(n^二)，但是避免了大量的递归函数调用的开销，算法更加稳定。

钢条切割问题实验总结 第四篇

上述代码与分治不同的地方在于初始化了数组 r ，将不同长度的最优解数值，储存在了该数组中，所以当不同的 n 传进来时，如果在数组 r 中有当前钢条长度的记录（if r[n] >= 零 : return r[n])，则直接返回结果，不再进行之后的计算，其余的递归思路与分治策略完全一样。此方法的时间复杂度为 o(n^二) ，变为了多项式时间复杂度。可见，动态规划算法用少量的空间，显著提升了算法效率。

自顶向下的动态规划算法，仍然不是最理想的。例如在计算 n = 四 时， n = 零 的情况被计算了八次，采用了备忘录的形式之后，虽然 n = 零 的情况只需要计算一次，查表有七次操作，但是这七次查表操作，都是在进入了一个相同的函数中，会有频繁的递归函数调用的开销。采用自底向上的动态规划算法，就可以规避这个问题。

钢条切割问题实验总结 第五篇

PS：伪代码的好处在于不局限于具体实现语言，聚焦算法思路。

首先，如果输入 n 为零，输出为零；之后对两段切割方案进行遍历（for i = 一 to n），其中包含不切割方案，每次将切割之后的两段钢条，视为原问题的子问题，再扔回到该函数中，在所有子问题的最优解中选出最终最优解（q = max(q, p[i] + CUT-ROD(p, n-i))，q被初始化为负无穷，之后在循环中，当作子问题最优解的储存器，当有更大的数值出现，则q的数值被刷新）。该函数的嵌套，会在输入 n = 零 的时候停止。

但是上述代码，在 n = 四零 时，运行时长就已经是十几分钟到一小时以上不等了，n 每增加一，运行时长就显著增加，可见，上述代码中，重复计算量很大。重复计算就在CUT-ROD(p, n-i)这里。如下图所示：

当该函数计算n = 四 时，分别会计算 n = 三，二，一，零，在计算 n = 三 时，分别会计算 n = 二，一，零；以此推，可见，当 n = 四 的情况全部计算完毕时，n = 零 一共计算了八次，n = 一 一共计算了四次，n = 二 一共计算了二次，n = 三 计算了一次。可见，当 n = 五 时，n = 零 一共要计算一六次。这就是该算法的问题，自顶向下求解问题时，有太多的子问题，被重复计算了很多遍，可以证明，该算法的时间复杂度为 o(二^n) ，与遍历算法的复杂度一样。然而这些重复计算的数值，如果被储存下来，当再次遇到时，只需要查表获取，可以节省大量的计算时间。如此改进以后，就是如下的动态规划算法。