钢条切割问题——动态规划

钢条切割问题——利用动态规划进行求解

1. 钢条切割问题就是指给定一段长度为n的钢条&＃xff0c;在钢条不同位置上进行切割&＃xff0c;总长度不变&＃xff0c;切割成本为0&＃xff0c;求切割后钢条的最大收益

动态规划代码&＃xff1a;

def RobCutting(p, n):""":param p:钢条价格表:param n:钢条长度:return:切割钢条得到的最大收益C[n]&＃xff0c;钢条切割方案"""# 初始化C &＃61; [0 for _ in range(n &＃43; 1)] # 这里C为收益列表&＃xff0c;当n为0时&＃xff0c;收益为0&＃xff0c;即C[0]&＃61;0rec &＃61; [None for _ in range(n &＃43; 1)] # 这里是追踪列表C[0] &＃61; 0# 动态规划for j in range(1, n &＃43; 1): q &＃61; p[j - 1]rec[j] &＃61; jfor i in range(1, j):if q < p[i - 1] &＃43; C[j - i]:q &＃61; p[i - 1] &＃43; C[j - i]rec[j] &＃61; iC[j] &＃61; qprint("不同钢条长度的收益&＃xff1a;", C)print("最优追踪方案&＃xff1a;", end&＃61;&＃39; &＃39;)# 输出最优追踪方案while n > 0:print(rec[n], end&＃61;&＃39; &＃39;)n -&＃61; rec[n]
if __name__ &＃61;&＃61; &＃39;__main__&＃39;:p &＃61; [1, 5, 8, 9, 10, 17, 17, 20, 24, 24]print(RobCutting(p, n&＃61;10))