钢条切割问题实验总结.docx

钢条切割问题实验总结第1篇
钢条切割问题实验总结第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中有当前钢条长度的记录（ifr[n]>=0:returnr[n])，则直接返回结果，不再进行之后的计算，其余的递归思路与分治策略完全一样。此方法的时间复杂度为o(n^2)，变为了多项式时间复杂度。可见，动态规划算法用少量的空间，显著提升了算法效率。自顶向下的动态规划算法，仍然不是最理想的。例如在计算n=4时，n=0的情况被计算了8次，采用了备忘录的形式之后，虽然n=0的情况只需要计算1次，查表有7次操作，但是这7次查表操作，都是在进入了一个相同的函数中，会有频繁的递归函数调用的开销。采用自底向上的动态规划算法，就可以规避这个问题。钢条切割问题实验总结第5篇PS：伪代码的好处在于不局限于具体实现语言，聚焦算法思路。首先，如果输入n为0，输出为0；之后对两段切割方案进行遍历（fori=1ton），其中包含不切割方案，每次将切割之后的两段钢条，视为原问题的子问题，再扔回到该函数中，在所有子问题的最优解中选出最终最优解（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次。这就是该算法的问题，自顶向下求解问题时，有太多的子问题，被重复计算