本文共 4745 字，大约阅读时间需要 15 分钟。

钢条切割问题

1. 问题

某公司出售钢条，出售价格与钢条长度之间的关系如下表:

问题:现有一段长度为n的钢条和上面的价格表，求切割钢条方案，使得总收益最大。

2. 思路

思考: 长度为n的钢条的不同切割方案有几种?

有$2^{n-1}$种，因为有$n-1$个可以切割的地方，每个位置都有切与不切两种选择，所以是$2^{n-1}$种，但是这种方法不太合适，因为如果n太大的时候，切割方案会指数爆炸，效率不高。

2.1 最优子结构

    昨天有讲动态规划，动态规划(DP)的思想 = 最优子结构(递推式) + 重复子问题，那么我们可以看看这道题目的最优子结构:

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

最优子结构(大的问题切割为小的子问题，如果子问题有最优解并且这些最优解解能算大问题的解，即最优子结构)

2.2 递推式

我们再来看看这道问题的递推式:

设长度为n的钢条切割后最优收益值为rn，可以得出递推式: $r_n=max(p_n,r_1+r_{n-1},r_2+r_{n-2},...,r_{n-1}十r_1)$ 第一个参数$p_n$表示不切割，其他$n-1$个参数分别表示另外$n-1$种不同切割方案，对方案$i=1,2...n-1$，将钢条切割为长度为$i$和$n-i$两段，方案i的收益为切割两段的最优收益之和，考察所有的$i$，选择其中收益最大的方案！

3. 代码

从递推式，我们想到可以用递归求解！有结束条件，又是调用自身

'''TOPIC: 钢条切割: 递归实现author: Bluetime: 2020-08-19QQ: 2458682080'''# 价格列表，下标即为长度p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]def cut_rod_recurision_1(p, n):    if n == 0:        return 0    else:        res = p[n]        for i in range(1, n):            res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i))            # 递归2次，所以慢        return resprint(cut_rod_recurision_1(p, 10))

结果为: 30，即当钢条长度n=10时，最大总收益为30！

4. 思路改进

昨天的博客里说到了，当n变大时，递归的效率其实也不高，那么有什么方法可以进行改进呢？我们想，上面的递推式，我们取的是$max(r_i+r_{n-i})$，即算当i确定时，就要进行两次递归，那么是不是可以减少递归的次数呢？

这里我们就进行改进：

1. 从钢条的左边切割下长度为i的一段，只对右边剩下的一段继续进行切割，左边的不再切割
2. 递推式简化为$r_n=\underset{1<j\le m}{\max }(p_i+r_{n-i})$
3. 不做切割的方案就可以描述为:左边一段长度为n，收益为$p_n$，剩余一段长度为0，收益为$r_0$=0。

这样对于每一个i，我们就减少了递归的次数，增加了效率！

5. 代码改进

# 简化后的算法def cut_rod_recurision_2(p, n):    if n == 0:        return 0    else:        res = 0        for i in range(1, n+1):            res = max(res, p[i] + cut_rod_recurision_2(p, n-i))  # 递归一次，所以快        return res

6. 思路再改进

其实我们思路改进后，还是用到了递归，只不过是减少了递归的使用次数而已，所以当n过大时，算法还是无法承受，效率不高。我们之前的两种方法，改进前以及改进后，都用到了递归，递推式分别为:

$r_n=max(p_n,r_1+r_{n-1},r_2+r_{n-2},...,r_{n-1}十r_1)$ $r_n=\underset{1<j\le m}{\max }(p_i+r_{n-i})$ 可以发现，这两种方法都是自上而下的切割方法。什么叫做自上而下的切割方法呢？就是把长度为n的进行切割为两段，再分别计算两段的最优价值，就这样，一步一步切割，一步一步计算，最后到不能切割为止，得到结果！时间复杂度为$O(2^n)$! 那这里，我们就提出了 动态规划(DP)的思路 ： 自底向上的方法: 从短到长，把长度从0~n的钢条最优价格求出来，因为每次求出长度后都用列表储存，所以计算后面的长度时，直接从列表里取出相应切割方案对应的价值，相加即可，不需要递归，大大增加了效率！

7. 代码再改进

def cut_rod_dp(p, n):    r = [0]    for i in range(1, n+1):  # 下标i对应的数字就是长度为n=i的钢条的最优价格，所以i从1开始，把长度从1~n的钢条最优价格求出来        res = 0        for j in range(1, i+1):  # 求当n确定时，利用递推式求出此时的最优价格            res = max(res, p[j] + r[i - j])        r.append(res)    return r[n]

思路很简单，代码也很简单！

当然，有了最大价值，我们还需要知道切割方案：

'''TOPIC: 钢条切割: 自顶向下实现author: Bluetime: 2020-08-19QQ: 2458682080'''# 重构解def cut_rod_extend(p, n):    r = [0]    s = [0]    for i in range(1, n+1):  # 下标i对应的数字就是长度为n=i的钢条的最优价格，所以i从1开始        res_r = 0  # 记录价格的最大值        res_s = 0  # 记录价格最大值对应方案的左边不切割部分的长度        for j in range(1, i+1):            if p[j] + r[i - j] > res_r:                res_r = p[j] + r[i - j]                res_s = j        r.append(res_r)        s.append(res_s)    return r[n], s# 获取切割方案def cut_rod_solution(p, n):    r, s = cut_rod_extend(p, n)    ans = []    while n > 0:        ans.append(s[n])        n -= s[n]    return ans

所有代码为:

# 自底向上的方法def cut_rod_dp(p, n):    r = [0]    for i in range(1, n+1):  # 下标i对应的数字就是长度为n=i的钢条的最优价格，所以i从1开始，把长度从1~n的钢条最优价格求出来        res = 0        for j in range(1, i+1):  # 求当n确定时，利用递推式求出此时的最优价格            res = max(res, p[j] + r[i - j])        r.append(res)    return r[n]# print(c2(p, 20))# print(cut_rod_dp(p, 20))# 重构解def cut_rod_extend(p, n):    r = [0]    s = [0]    for i in range(1, n+1):  # 下标i对应的数字就是长度为n=i的钢条的最优价格，所以i从1开始        res_r = 0  # 记录价格的最大值        res_s = 0  # 记录价格最大值对应方案的左边不切割部分的长度        for j in range(1, i+1):            if p[j] + r[i - j] > res_r:                res_r = p[j] + r[i - j]                res_s = j        r.append(res_r)        s.append(res_s)    return r[n], s# 获取切割方案def cut_rod_solution(p, n):    r, s = cut_rod_extend(p, n)    ans = []    while n > 0:        ans.append(s[n])        n -= s[n]    return ansr, s = cut_rod_extend(p, 20)print(s)print(cut_rod_dp(p, 20))

结果为:

[0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10]  # 切割方案30  # 最大价值

钢条切割问题——自底向上递归实现

时间复杂度O(n^2)

8. 总结

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

递归算法由于重复求解相同子问题，效率极低 动态规划的思想:

1. 每个子问题只求解一次，保存求解结果
2. 之后需要此问题时，只需查找保存的结果

动态规划问题关键特征

什么问题可以使用动态规划方法?

1. 最优问题
2. 最优子结构
   • 原问题的最优解中涉及多少个子问题
   • 在确定最优解使用哪些子问题时，需要考虑多少种选择
3. 重叠子问题

转载地址：http://wdiwi.baihongyu.com/