1、钢条切割问题：

• 某公司出售钢条，出售价格与钢条长度的关系如下表：
  
• 问题：现有一段长度为n的钢条，请根据上面的介个表，求切割钢条方案，使得总收益最大

2、分析思路：

• 首先可以根据价格表计算出每个长度对应的最高收入，如下
  

• 钢条切割问题的递推式：
  

• 钢条切割问题的最优子结构

  • 可以将求解规模为n的原问题，划分为规模更小的子问题，完成一次切割后，可以将产生的两端钢条看成两个独立的钢条切割问题
  • 组合两个子问题的最优解，并在所有可能的两段切割方案中选择组合收益最大的，构成原问题的最优解
  • 钢条切割满足最优子结构：问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解

• 使用递归的方式代码实现如下：

def cut_rod_recurision(price,length):
    if length==0:
        return 0
    else:
        res=price[length]
        for i in range(1,length):
            res=max(res,cut_rod_recurision(price,i)+cut_rod_recurision(price,length-i))
        return res

if __name__=="__main__":
    price=[0,1,5,8,9,10,17,17,20,24,30]
    print(cut_rod_recurision(price,9))

执行结果如下：

25

• 递归的方式可以做一个优化，即左侧不需要继续拆分了，即直接使用price对应的值，代码如下：

def cut_rod_recurision(price,length):
    if length==0:
        return 0
    else:
        res=0
        for i in range(1,length+1):
            res=max(res,price[i]+cut_rod_recurision(price,length-i))
        return res

if __name__=="__main__":
    price=[0,1,5,8,9,10,17,17,20,24,30]
    print(cut_rod_recurision(price,9))

执行结果不变

• 上述使用递归的算法是一种自定而下的方法，它的时间复杂度为O（2ⁿ）

3、使用动态规划自底向上的算法

• 动态规划的思想：
  • 每个子问题只求解一次，保存求解结果
  • 之后需要此问题时，只需要查找保存的结果
    代码实现如下：

def cut_rod_dp(price,length):
    r=[0]
    for i in range(1,length+1):
        res=0
        for j in range(1,i+1):
            res=max(res,price[j]+r[i-j])
        r.append(res)
    return r[length]



if __name__=="__main__":
    price=[0,1,5,8,9,10,17,17,20,24,30]
    print(cut_rod_dp(price,9))

执行结果如下：

25

• 动态规划的算法的时间复杂度为O（n²）

• 为了给出最终的切割方案，需要另外多存一个列表，列表中存去左侧不能再分割的长度，如下：
  

• 如下代码给出了如何切割的方案

def cut_rod_dp(price,length):
    r=[0]
    s=[0]
    for i in range(1,length+1):
        res_r=0
        res_s=0
        for j in range(1,i+1):
            if price[j]+r[i-j]>res_r:
                res_r=price[j]+r[i-j]
                res_s=j
        r.append(res_r)
        s.append(res_s)
    return r[length],s

def cut_rod_solution(price,length):
    r,s=cut_rod_dp(price,length)
    ans=[]
    while length>0:
        ans.append(s[length])
        length-=s[length]
    return ans

if __name__=="__main__":
    price=[0,1,5,8,9,10,17,17,20,24,30]
    print(cut_rod_solution(price,9))

执行结果如下：

[3, 6]

• 什么问题可以使用动态规划方法
  • 原问题的最优解中设计多少个子问题
  • 在确定最优解使用哪些子问题时，需要考虑多种选择