作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
1. 问题介绍和应用场景
切割钢条问题是运筹学和算法设计中的一个经典问题，涉及如何最优化切割有限资源以最大化收益。这个问题经常用作动态规划教学的入门案例，同时在工业生产中也有实际应用，比如在金属加工业中如何切割原材料以减少浪费并增加销售利润。
2. 初阶问题-价值最大
定义：给定一根长度为 ( n ) 的钢条和一个价格表，表中列出了从长度 1 到 ( n ) 的每一种长度的钢条的售价。求切割方案，使得销售收益最大化。
示例：
- 钢条长度：4
- 价格表：{1:1, 2:5, 3:8, 4:9}
最优切割方案是切割为两段，每段长度为 2，销售收益为 ( 5 + 5 = 10 )。
状态定义
定义 dp[i] 为长度为 ( i ) 的钢条的最大销售收益。
状态转移方程
考虑每一种可能的切割第一刀的位置，状态转移方程为：
初始化和边界情况
- ( dp[0] = 0 )：长度为 0 的钢条没有收益。
算法实现
def cut_rod(price, n): dp = [0] * (n + 1) for i in range(1, n + 1): max_val = float('-inf') for j in range(1, i + 1): max_val = max(max_val, price[j] + dp[i - j]) dp[i] = max_val return dp[n] # 示例使用 price = {1: 1, 2: 5, 3: 8, 4: 9} n = 4 print("最大收益:", cut_rod(price, n)) # 输出: 最大收益: 10
复杂度分析
- 时间复杂度：O(n^2)，其中 ( n ) 是钢条的长度。需要计算每个长度的最优解，每次计算涉及遍历所有可能的切割点。
- 空间复杂度：O(n)，存储长度为 ( n ) 的
dp数组。
算法图解
为了进一步阐明“切割钢条”问题的动态规划解法，并辅以图解，我们将使用一个示例和配套的说明来详细解释每一步的计算过程。我们继续用整数数组 price = {1:1, 2:5, 3:8, 4:9} 和钢条长度 n = 4 来演示。
首先，我们初始化动态规划表 dp。表的每个单元格将代表长度为 (i) 的钢条的最大销售收益。
初始化
初始 dp 表：
| Length ((i)) | 0 | 1 | 2 | 3 | 4 |
| dp[i] | 0 | 0 | 0 | 0 | 0 |
dp[0] = 0：没有钢条时，收益为0。
填充过程
逐步计算每个长度的最大收益。
- 长度为 1:
- 只有一种切法，即不切，直接卖出。
dp[1] = price[1] = 1
- 长度为 2:
- 切为两个长度为 1 的钢条，或不切。
dp[2] = max(price[2], price[1] + dp[1]) = max(5, 1+1) = 5
- 长度为 3:
- 切为三个长度为 1 的钢条，切为一个长度为 1 和一个长度为 2 的钢条，或不切。
dp[3] = max(price[3], price[1] + dp[2], price[2] + dp[1]) = max(8, 1+5, 5+1) = 8
- 长度为 4:
- 切为四个长度为 1 的钢条，切为两个长度为 2 的钢条，切为一个长度为 1 和一个长度为 3 的钢条，或不切。
dp[4] = max(price[4], price[1] + dp[3], price[2] + dp[2], price[3] + dp[1]) = max(9, 1+8, 5+5, 8+1) = 10
最终填充的 dp 表：
| Length ((i)) | 0 | 1 | 2 | 3 | 4 |
| dp[i] | 0 | 1 | 5 | 8 | 10 |
图解说明
想象一个表格，行表示钢条长度，列代表不同的切割方案。每个单元格填入该切割方案的收益，最后选择每行中的最大值填入到 dp 表中。每次切割决策基于获取最大收益的需要。
+---------------------------------------+ | Length | Cut Scenario | +---------------------------------------+ | 1 | [1] -> 1 | | 2 | [1+1], [2] -> 5 | | 3 | [1+1+1], [1+2], [3] -> 8 | | 4 | [1+1+1+1], [2+2], [1+3], [4] -> 10 | +---------------------------------------+
3.进阶问题-最优切割方案
在讨论切割钢条问题或任何涉及资源分割的优化问题时，“最优切割方案”指的是通过合理分割资源（如钢条、织物等）以达到某个特定目标（如最大化利润、最小化浪费等）的一种策略或方案。在动态规划的上下文中，这通常涉及确定一系列决策，这些决策共同导致全局最优的结果。
最优切割方案的定义
在切割钢条的例子中，钢条有一定长度，每个长度有一个对应的市场价值。最优切割方案就是找到一种切割钢条的方式，使得从出售这些切割后的小段钢条所获得的总收益最大化。
关键组件
- 目标：最大化从出售切割后的钢条获得的收益。
- 决策：选择在哪些点切割钢条，包括决定每一段的长度。
- 状态：用于描述问题的某个阶段或条件，如钢条的当前长度。
- 状态转移：决策导致状态改变，进而更新问题的当前解的方式，如从更长的钢条到切割后的剩余部分。
如何找到最优切割方案
- 定义状态：
dp[i]表示长度为i的钢条的最大销售收益。
- 状态转移方程：
dp[i] = max(dp[i], price[j] + dp[i-j])，其中1 ≤ j ≤ i是可能的切割点，price[j]是长度j的钢条的价格。
- 记录切割点：
- 使用一个辅助数组
s[i]来记录获得dp[i]的最大收益时的首次切割点。
- 回溯切割方案：
- 从
s[n]开始回溯，其中n是钢条的总长度，通过连续查询s数组构建出全部的切割方案。
示例
假设有一根长度为 4 的钢条，价格表如下：
| 长度 | 1 | 2 | 3 | 4 |
| 价格 | 1 | 5 | 8 | 9 |
最优切割方案为两段，每段长度为 2，因为 5 + 5 = 10 是所有可能切割方案中收益最高的（切割为 1+1+1+1 的收益为 4，切割为 1+3 或 3+1 的收益为 9，不切割的收益为 9）。
通过定义动态规划的状态和决策过程，以及记录每个决策点，我们可以确定并回溯出达到最大收益的具体切割步骤，即最优切割方案。这种方法不仅减少了试错的需要，而且提供了一种系统的方式来解决问题。
总结
切割钢条问题通过动态规划提供了一种有效的解决方案，能够处理资源优化问题并可扩展到更复杂的场景中。这种方法不仅提升了问题解决的效率，也增强了理解动态规划的直观性和实用性。掌握这种基础的动态规划应用能够帮助解决更广泛的优化问题，是算法学习和应用中的重要步骤。
欢迎关注微信公众号 数据分析螺丝钉
