切割棒材以实现利润最大化的算法

Question

我正试图通过动态编程来解决标准的棒材切割问题。正如在这里和这里发现的，递归关系似乎是：

prices = [1..n]
array[1..n]
array[1] = prices[1]
for i in (2..n)
{
    array[i] = INT_MIN
    for j in (1..i-1)
    {
        array[i] = max(array[i],prices[j]+array[i-j])
    }
}

array[n]返回n的值，这就是我们的答案。我的问题在于

array[i] = max(array[i],prices[j]+array[i-j])

不应该是吗

array[i] = max(array[i],array[j]+array[i-j])

假设我们试图找到长度8的最大值。现在，对于4，我们发现通过切割单个长度单位4获得的值小于通过切割3和1的长度获得的值，即对于n = 4，prices[4]不是最优的。但由于我们是自下而上构建结果数组，因此array[4]是最优的。那么，与prices[4]+array[4]相比，array[4]+array[4]不是n = 8的最大值吗？我得到的解决方案如下：

prices = [1..n]
array[1..n]
for i in (1..n)
    array[i] = prices[i] //prices[i] is the minimum value we can obtain by cutting it fully 
for i in (2..n)
{
    for j in (1..i-1)
    {
        array[i] = max(array[i],array[j]+array[i-j]) // find out all possible (j,i-j) pairs, and compare with array[i]
    }
}

如果这不正确，请告诉我我在哪里犯了逻辑错误。

Answer 1

array[i] = max(array[i],prices[j]+array[i-j])看起来很对。

在该算法中，j表示初始切割的杆的长度。我们从长度为i的杆开始，并切断j。然后，我们需要知道一根i - j的杆能得到多少，因为你只需切掉j的长度，就剩下i - j了。但我们知道这个值至少和price[i-j]一样高，因为我们可以选择将棒作为一个整体出售，也可以通过切割来增加其价值。

示例：我们有一根长度为4的杆子。假设数组[]已经包含1,2,3的最优值，则我们：

剪下一块长度为1的棍子，然后检查我们能得到一根长度为3的的多少

剪下一块长度为2的，然后检查我们能得到多少对于长度为2 的棒

剪下一块长度为3的棍子，然后检查我们能得到一根长度为1的的多少

并选择最大值。

如果我们使用array[i] = max(array[i],array[j]+array[i-j])

如果我们将长度为k的杆切成块，则array[k]包含最大值。因此，与使用price[k]相比，这些值会出乎意料地高。

此外，递归中的当前步骤只关心进行一次切割，并检查剩余部分的最大值，而不是两侧的最大值（当您发现大切割的值可能不理想时，会进行处理）