[数据结构与算法]钢条切割问题——动态规划

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

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

动态规划代码：

def RobCutting(p, n):
	"""

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