数据结构(python) |
您所在的位置：网站首页 › 综合治理工作年度总结 › 数据结构(python) |
数据结构(python)
|
钢条切割问题
1. 问题
某公司出售钢条，出售价格与钢条长度之间的关系如下表: 思考: 长度为n的钢条的不同切割方案有几种? 有 2 n − 1 2^{n-1} 2n−1种，因为有 n − 1 n-1 n−1个可以切割的地方，每个位置都有切与不切两种选择，所以是 2 n − 1 2^{n-1} 2n−1种，但是这种方法不太合适，因为如果n太大的时候，切割方案会指数爆炸，效率不高。 2.1 最优子结构昨天有讲动态规划，动态规划(DP)的思想 = 最优子结构(递推式) + 重复子问题，那么我们可以看看这道题目的最优子结构: 可以将求解规模为n的原问题，划分为规模更小的子问题:完成一次切割后，可以将产生的两段钢条看成两个独立的钢条切个问题。组合两个子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大的，构成原问题的最优解。钢条切割满足最优子结构:问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解。最优子结构(大的问题切割为小的子问题，如果子问题有最优解并且这些最优解解能算大问题的解，即最优子结构) 2.2 递推式我们再来看看这道问题的递推式: 设长度为n的钢条切割后最优收益值为rn，可以得出递推式: r n = m a x ( p n , r 1 + r n − 1 , r 2 + r n − 2 , . . . , r n − 1 十 r 1 ) r_n=max(p_n,r_1 +r_{n-1},r_2+r_{n-2},...,r_{n-1}十r_1) rn=max(pn,r1+rn−1,r2+rn−2,...,rn−1十r1) 第一个参数 p n p_n pn表示不切割，其他 n − 1 n-1 n−1个参数分别表示另外 n − 1 n-1 n−1种不同切割方案，对方案 i = 1 , 2... n − 1 i=1,2...n-1 i=1,2...n−1，将钢条切割为长度为 i i i和 n − i n-i n−i两段，方案i的收益为切割两段的最优收益之和，考察所有的 i i i，选择其中收益最大的方案！ 3. 代码从递推式，我们想到可以用递归求解！有结束条件，又是调用自身 ''' TOPIC: 钢条切割: 递归实现 author: Blue time: 2020-08-19 QQ: 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 res print(cut_rod_recurision_1(p, 10))结果为: 30，即当钢条长度n=10时，最大总收益为30！ 4. 思路改进昨天的博客里说到了，当n变大时，递归的效率其实也不高，那么有什么方法可以进行改进呢？我们想，上面的递推式，我们取的是 m a x ( r i + r n − i ) max(r_i +r_{n-i}) max(ri+rn−i)，即算当i确定时，就要进行两次递归，那么是不是可以减少递归的次数呢？ 这里我们就进行改进： 从钢条的左边切割下长度为i的一段，只对右边剩下的一段继续进行切割，左边的不再切割递推式简化为 r n = max 1 < j ≤ m ( p i + r n − i ) r_n=\max\limits_{1 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 ans r, 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. 总结钢条切割问题——动态规划解法 递归算法由于重复求解相同子问题，效率极低 动态规划的思想: 每个子问题只求解一次，保存求解结果之后需要此问题时，只需查找保存的结果动态规划问题关键特征 什么问题可以使用动态规划方法? 最优问题最优子结构 原问题的最优解中涉及多少个子问题在确定最优解使用哪些子问题时，需要考虑多少种选择 重叠子问题 |
问题:现有一段长度为n的钢条和上面的价格表，求切割钢条方案，使得总收益最大。【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |