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（2n）
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（n2）
-
为了给出最终的切割方案，需要另外多存一个列表，列表中存去左侧不能再分割的长度，如下：
-
如下代码给出了如何切割的方案
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]
- 什么问题可以使用动态规划方法
- 原问题的最优解中设计多少个子问题
- 在确定最优解使用哪些子问题时，需要考虑多种选择
