查找棒材切割的价格

Question

给定杆的长度和前 3 根杆的 P（价格）。我们要填写我们可以为其余的杆获得的可能价格。假设我们可以根据需要切割较长的部分。

L = 1     2       3      4       5        6         7          8 
p = 3     8       12

我们基本上想得到每个缺失长度价格所能得到的最高价格。

我的做法 我相信，由于我们得到了长度为 1,2 和 3 的杆的最佳可能价格，我们可以为下一根杆生成所有可能的组合。

For example to get price of rod where L = 4 
price of rod where L = 1 + rod where L =  3 = 15
price of rod where L =  2 + rode where L =  2 = 16
Therefore price of rod wehre L = 4  = 16 since 16 > 15.

For example to get price of rod where L = 5
price of rod where L = 1 + rod where L = 2 and rod where L = 2 = 19
price of rod where L = 3 + rod where L = 2  = 20
price of rod where L = 4 + rod where L = 1 = 19

这就是我正在遵循的方法。但是我不确定我是否正确。如果有人可以验证这种方法并且也可以帮助我从中推导出一个公式，我也希望如此。我不是在寻找代码，因为了解问题足以编写代码。

Answer 1

您可以在 CLRS（第 15.1 节，第 360 页）中查看此问题变体的解释。这个问题叫做棒切割问题。

你的做法是对的，可以形式化为递归关系。

f(n) = min(f(n - i) + price(i)).    1 <= i <= n - 1

其中 f(n) 是购买长度为 n 的杆的最低价格。使用记忆，这可以在 O(n^2).

中计算

Answer 2

你的做法是正确的。也可以按照 MrGreen ()

的回答以另一种方式完成

设，B(i) = 切割长度为 i 单位的杆的最优价格，p(i) = 长度为 i 单位的杆的价格。

公式 1：B(i) = max(1<=k<=floor(i/2)) {B(k) + B(i-k)} 和 P(i)

公式 2：B(i) = max(1<=k<=i) {p(k) + B(i-k)})

考虑一根长度为 4 的杆，可以通过以下方式切割它：

1) 未切割长度 4

2) 3, 1

3) 2, 2

4) 2, 1, 1

5) 1, 3

6) 1, 2, 1

7) 1, 1, 2

8) 1, 1, 1, 1

根据公式1：

选项1对应P(4)

选项2,5,6,7,8对应B(1) + B(3)

选项3,4,6,7,8对应B(2) + B(2)

根据公式2：

选项1对应P(4)

选项2对应P(3)+B(1)

选项3,4对应P(2)+B(2)

选项5,6,7,8对应P(1) + B(3)

总而言之，1 和 2 正在计算最优解，但计算方式不同，其中 2 与 1 相比更紧凑，递归调用更少。

查找棒材切割的价格

Find price for Rod cutting

algorithm

dynamic-programming