切割杆最大化利润的算法 [英] Algorithm for cutting rod to maximize profit

问题描述

我正在尝试通过动态编程来解决标准的杆切割问题.如此处和

I am trying to solve the standard rod-cutting problem through dynamic programming. As found here and here, the recurrence relations seems to be:

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的值，这就是我们的答案.我的问题就在这行

And array[n] returns the value for n, which is our answer. My question lies in the line

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的最大值吗?我得到的解决方案看起来像这样:

Imagine we are trying to find max value for length 8. Now, for 4 we find that the value we obtain by cutting one single unit of length 4 is less than say obtained by cutting lengths of 3 and 1, i.e for n = 4, prices[4] is not optimal. But since we are building the result array bottom up, array[4] is optimal. So won't array[4]+array[4] be the max value for n = 8, compared to prices[4]+array[4]? My resulting solution looks something like this:

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]
    }
}

如果这不正确，请告诉我我在哪里犯错了.

If this is not correct, please tell me where am I erring logically.

推荐答案

array[i] = max(array[i],prices[j]+array[i-j])对我来说正确.

在该算法中，j表示初始切割的棒的长度.我们从长度为i的杆开始，然后切除j.然后，我们需要知道对于i - j杆，我们能得到多少，因为您只是切断了j的长度，而剩下的却是i - j.但是我们知道该值至少与price[i-j]一样高，因为我们可以选择整体出售该杆，也可以通过切割杆以增加其值.

In that algorithm, j represents the length of rod of your initial cut. We start off with a rod of length i and cut off j. Then, we need to know how much we can get for a rod of i - j because you just cut off j length and you're left with i - j. But we know this value is at least as high as price[i-j] because we have the option of selling the rod as a whole or by cutting it to increase its value.

示例: 我们有一根长度为4的杆.假设array []已经包含1,2,3的最优值，那么我们:

Example: We have a rod of length 4. Assuming array[] already contains optimal values for 1,2,3, then we:

切下一块长度为1的棒，然后检查一下长度为3的棒能得到多少

cut off a piece of length 1, then check how much we can get for a rod of length 3

剪掉一段长度为2的片段，然后检查我们可以得到多少 长度为2的杆

cut off a piece of length 2, then check how much we can get for a rod of length 2

切下一块长度为3的棒，然后检查一下长度为1的棒能得到多少

cut off a piece of length 3, then check how much we can get for a rod of length 1

然后选择最大值.

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

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

array[k] contains the maximum value for a rod of length k if we cut it into pieces. So these values would be unexpectedly high compared to if we used price[k].

此外，递归中的当前步骤仅关心进行一次剪切，并检查剩余的最大值，而不是两边的最大值(当您发现大剪切的值可能不理想时，将注意这一点. )

Also the current step in the recursion only cares about making one cut, and checking the leftover's max value, not both sides max values (that will be taken care of when you find that the value of a large cut may not be ideal)

这篇关于切割杆最大化利润的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！