RodCutting [棒材切割问题]
# 介绍
给你一根长度为 n 的杆子和一个与所有长度小于 n 的价格数组。通过切割杆子和出售这些杆子，找出可能的最大利润。
# 递归法
我们得到一个数组 price []，其中长度的杆 i 有价值 price [i-1]. 这个想法很简单 —— 一根一根地分割给定的长度棒 n 分为两部分： i 和 n-i。重复分割 n-1 长度的棒，但不要分割长度为 i 的棒。最后，取所有值中的最大值。这产生以下递归的关系： rodcut(n) = max { price[i – 1] + rodCut(n – i) } where 1 <= i <= n 。
def rodCut(price, n):
if n == 0:
return 0
maxValue = -sys.maxsize
# 将给定的长度为`n`的杆分成两部分长度
# (1, n-1), (2, n-2), (3, n-3), … ,(n-1, 1), (n, 0) 取最大值
for i in range(1, n + 1):
# 长度为 `i` 的杆的成本为 `price[i-1]`
cost = price[i - 1] + rodCut(price, n - i)
if cost > maxValue:
maxValue = cost
return maxValue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
上述解决方案的时间复杂度为 O (nn) 并占用调用堆栈中的空间，其中 n 是杆长。
我们已经看到问题可以分解为更小的子问题，这些子问题可以进一步分解为更小的子问题，依此类推。所以，问题有最优子结构。让我们考虑一个长度为 4 的杆的递归树。
正如我们所看到的，相同的子问题 (以相同的颜色突出显示) 被重复计算。所以，重叠子问题特征也表现出来了。我们知道具有最优子结构和重叠子问题的问题可以通过动态规划来解决，其中子问题的解决方案是缓存化而不必重复计算。
# 动态规划法
动态规划和分治法的区别：
- 分治法是将问题划分成一些独立的子问题，递归求解各个子问题，然后合并子问题的解而得到原问题的解
- 动态规划使用于子问题不独立的情况，也就是各个子问题包含公共的部分。若采用分治法，会有重复的求解公共部分，而动态规划算法对每个子问题只求解一次，然后将结果保存在一张表中，从而避免重复的运算。
动态规划具有如下特征：
- 最优子结构
- 重叠子问题
动态规划算法设计可以分为如下步骤：
- 描述最优解的结构
- 递归定义最优解的值
- 按自底向上的方式计算最优解的值
- 由计算出的结果构造一个最优解
我们将以自下而上的方式解决这个问题。在自下而上的方法中，我们首先解决较小的子问题，然后从中解决较大的子问题。以下自下而上的方法计算 T [i]，它存储从长度为 i 的杆获得的最大利润。
def rodCut(price, n):
T = [0] * (n + 1)
for i in range(1, n + 1):
for j in range(1, i + 1):
T[i] = max(T[i], price[j - 1] + T[i - j])
return T[n]
1
2
3
4
5
6
2
3
4
5
6
上述自下而上解的时间复杂度为 O (n^2) 并要求 O (n) 额外的空间，其中 n 是杆长。
# 实现
# JavaScript
/*
* You are given a rod of 'n' length and an array of prices associated with all the lengths less than 'n'.
* Find the maximum profit possible by cutting the rod and selling the pieces.
*/
function rodCut (prices, n) {
const memo = new Array(n + 1)
memo[0] = 0
for (let i = 1; i <= n; i++) {
let maxVal = Number.MIN_VALUE
for (let j = 0; j < i; j++) maxVal = Math.max(maxVal, prices[j] + memo[i - j - 1])
memo[i] = maxVal
}
return memo[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 参考
编辑 (opens new window)
上次更新: 2022/10/27, 20:28:55