lundi 23 mars 2020

Rod Cutting Problem (Confusion about price and revenue)

If you are familiar with the rod cutting algorithm, the question is at the bottom.

In the following algorithm (C++ code), rev is the array containing the maximum revenue a rod of given length could have, while the price array is for the standard price without cutting the rod into further pieces. The algorithm given below is what I am finding from many sources to find the maximum revenue of a rod of length n.

    int cutRod(int price[], int n) 
    { 
       int rev[n+1]; 
       rev[0] = 0; 
       int i, j; 
       for (i = 1; i<=n; i++) 
       { 
           int max_val = INT_MIN; 
           for (j = 0; j < i; j++) 
              max_val = max(max_val, price[j] + rev[i-j-1]); 
           val[i] = max_val; 
       } 
       return val[n]; 
    } 

As can be seen, this algorithm works by cutting the rod into two pieces where one piece is not cut further (we consider its price) while the other piece may be cut (we consider its revenue). This means we would need to do this for n times considering different lengths to cut.

QUESTION: Why can't we have this loop run half the number of iterations by passing only revenue of both the pieces rather than one price and one revenue, because revenue holds the information about whether the price is maximum if the rod is cut or if it is not cut? Wouldn't that be more efficient? Simply put: price[1]<=rev[1], price[2]<=rev[2], ... So for rod of length n=3, instead of finding the maximum out of: price[1]+rev[2], price[2]+rev[1], price[3]+rev[0] (n elements) we could just find the maximum of: rev[1]+rev[2],rev[3]+rev[0] (⌊n/2⌋ + 1 elements)

Aucun commentaire:

Enregistrer un commentaire