Rod Cutting - Dynamic Programming

问题:

Problem Statement

---

The rod-cutting problem is the following. Given a rod of length n inches and a table of prices Pi for i = 1, 2, 3,....n, determine the maximum revenue Rn obtain- able by cutting up the rod and selling the pieces. Note that if the price Pn for a rod of length n is large enough, an optimal solution may require no cutting at all.

Consider the case whenn=4. Figure shows all the ways to cut up a rod of 4 inches in length, including the way with no cuts at all. We see that cutting a 4-inch rod into two 2-inch pieces produces revenue P2+P2=5+5=10, which is optimal.

The below code is a bottom-up approach of building the solution for rod-cutting.

for (i = 1; i<=n; i++)
{
   int q = INT_MIN;
   for (j = 0; j < i; j++)
       q= max(q, p[j] + r[i-j-1]);
   r[i] = q;
}
return val[n];

Why do we need an auxiliary array r[n+1]? Couldn't the problem be solved only by using just array p? Is it used because we cannot access p[-1] when we are cutting of rod length n and 0? Why are we using q = max(q, p[j] + r[i-j-1]) when p is not updated to new values?

回答1:

You should use two different arrays r and p, because their meaning is completely different. The value p[i] tells you, how much a complete (not cut) board of length i+1 costs. The value r[i] tells you, how much profit you can make with a board of length i+1 (complete or cut into pieces). These values are not the same. For instance in you example you have p[3] = 9, but r[3] = 10, because you can cut the board of length 4 into two smaller pieces of length 2. Keeping the two different meanings in separate arrays is most always a good idea. (Except if you have very tight memory restrictions)

Also, in practice you will likely not sell boards of length 100. But you might want to know the optimal profit, that you can make with a board of this size by cutting it. If you only have one array, you would have to enlarge it. Depending one your language choice this also might involve creating a second array and copying the first array. So it would be easier to simply use a second array.

Notice, that it is possible though (if n is smaller than the langth of the array p). A simple solution that uses only one array would be (using one-indexed):

int p[]={0,1,5,8,9,10,17,17,20,24,30};
int n = 4;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= i/2; j++)
        p[i] = max(p[i], p[j] + p[i - j]);
}
printf("%d\n", p[n]);

回答2:

If I understood the question correctly, then it is impossible to remove r from the implementation. Apparently the semantics of r is

r[i] = maximum profit attainabble by cutting a rod of length i
       into pieces of the lengths 1,...,n

and it needs to be accessed in the inner loop. The recurrence relation in the inner loop translates to

q = the more profitable choice between not cutting a rod of length j
    and cutting a rod of length j (in which case we take p[j] as
    profit plus the maximum attainable profit of cutting the remaining
    rod, which has length j-i)

which means that the information in r is necessary for the evaluation.

回答3:

Rod cutting problem without using auxiliary array in the inner loop and iterating it only by half.

#include <stdio.h>
#include <limits.h>

int max(int a,int b)
{
    return a>b?a:b;
}

int cut_rod(int p[],int n)
{
    int q=0;
    int r[n+1];   // Auxiliary array for copying p and appending 0 at index 0
    int i,j;

    if(n<0)
        return 0;
    else
    {
        r[0]=0;
        for(i=0;i<n;i++)
            r[i+1]=p[i];
        for(i=1;i<=n+1;i++)
        {
            q=INT_MIN;
            for(j=0;j<=i/2;j++)
                q=max(q,r[j]+r[i-j-1]);
            r[i-1]=q;
        }
    }
    return r[n];
}

int main()
{
    int p[]={1,5,8,9,10,17,17,20,24,30};
    int n=sizeof(p)/sizeof(int);
    int val;

    val=cut_rod(p,n);
    printf("%d",val);

    return 0;
}