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

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

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

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

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

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

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

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

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

2.切割为三段，长度为：1，1，2；总共卖2*1+1*5=7元。

3.切割为两段，长度为：1，3；总共卖1*1+1*8=9元。

4.切割为两段，长度为：2，2；总共卖2*5=10元。

5.不切割，长度为：4；总共卖1*9=9元。

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

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

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

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

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

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

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

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

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

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

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

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

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