Question

Give pseudocode for the rod-cutting optimization problem using the bottom-up approach and the top-down approach

Answer 1

Rod cutting is another kind of problem which can be solved without using dynamic programming approach but we can optimize it greatly by using it. According to the problem, we are provided with a long rod of length n units. We can cut the rod in different sizes and each size has a different cost associated with it i.e., a rod of i units length will have a cost of ci$.

Pseudo code and explanation for Top Down Code for Rod Cutting

We need the cost array (c) and the length of the rod (n) to begin with, so we will start our function with these two - TOP-DOWN-ROD-CUTTING(c, n)

We already know that we are going to use dynamic programming, so we will start by making an array to store the maximum revenue that can be generated by different lengths i.e., r[n+1] so that we don't have to recalculate this value again and again.

Initially, we don't know the value of the maximum revenue that can be generated by these lengths, so we will set all the elements of this array to something negative i.e., −∞. We can't initialize all the elements with 0 because the maximum revenue generated by the rod of length 0 is 0, so we will make the r[0] = 0.

r[0] = 0

for i in 1 to n

  r[i] = -INF

In the top down approach, we just start solving the problem naturally, so we will just start checking if the there is already a solution stored in the array or not.

if r[n] >= 0

  return r[n]

If the revenue is not already in the array r, then we will have to calculate it and for that, we need to calculate the maximum value among

(ci+rn−i)

for i ranging from 1 to n. Basically,

(ci+rn−i)

means the ci + maximum revenue that can be generated by rod of length n-i i.e., TOP-DOWN-ROD-CUTTING(c, n-i). Take note that we can't directly use the array r to get the value of r[n-i] because the array r doesn't store this value yet or at least we are not sure that it does or doesn't. This would have been in the case of bottom-up implementation in which we start by generating the smaller values first.

Now, the calculation of the maximum of (ci+rn−i) is similar to calculating the sum of all the elements of an array. We will have a variable to store the maximum revenue and then we will iterate from 1 to n and compare the current maximum revenue stored in the variable with the revenue c[i] + TOP-DOWN-ROD-CUTTING(c, n-i).

maximum_revenue = -INF

for i in 1 to n

  maximum_revenue = max(maximum_revenue, c[i] + TOP-DOWN-ROD-CUTTING(c, n-i))

As stated, we started by having a variable to store the maximum revenue i.e., maximum_revenue = -INF and then we iterate from 1 to n to find the maximum among c[i]+TOP-DOWN-ROD-CUTTING(c, n-i).

At last, we have to just fill up our array r and return this value.

r[n] = maximum_revenue

return r[n]

r[n+1]

r[0] = 0

for i = 1 to n

  r[i] = -INF

TOP-DOWN-ROD-CUTTING(c, n)

  if r[n] >= 0

    return r[n]

  maximum_revenue = -INF

  for i in 1 to n

    maximum_revenue = max(maximum_revenue, c[i] + TOP-DOWN-ROD-CUTTING(c, n-i))

  r[n] = maximum_revenue

  return r[n]

C Code:

#include <stdio.h>

#define MAX(x, y) (((x) > (y)) ? (x) : (y))

const int INF = 100000;

int r[5+1];

void init_r() {

  int i;

  r[0] = 0;

  for(i=1; i<=5; i++) {

    r[i] = -1*INF;

  }

}

int top_down_rod_cutting(int c[], int n) {

  if (r[n] >= 0) {

    return r[n];

  }

  int maximum_revenue = -1*INF;

  int i;

  for(i=1; i<=n; i++) {

    maximum_revenue = MAX(maximum_revenue, c[i] + top_down_rod_cutting(c, n-i));

  }

  r[n] = maximum_revenue;

  return r[n];

}

int main() {

  init_r();

  // array starting from 1, element at index 0 is fake

  int c[] = {0, 10, 24, 30, 40, 45};

  printf("%d\n", top_down_rod_cutting(c, 5));

  return 0;

}

Pseudo code and explanation for Bottom-Up Code for Rod Cutting

In the bottom-up technique, we start by filling the array from start. So, we will first initialize an array r and then we will iterate over it to fill it.

r[n+1]

r[0] = 0

for i in 1 to j

Now, the array r contains the maximum revenue that can pe generated by each length. For example, the 4th element of the array r contains the maximum revenue that can be generated by a rod of 4 units long. So to calculate it, we need to calculate the maximum of (ci+rn−i) for i ranging from 1 to 4. And thus, we need to iterate again for the different values of i.

for i in 1 to j

  max_revenue = -INF

  for i in 1 to j

    max_revenue = max(max_revenue, c[i] + r[j-i])

  r[j] = max_revenue

return r[n]

Take a note that we can directly use the value stored in the array r for

rn−i

because we know that we have already filled all the smaller values of the array.

BOTTOM-UP-ROD-CUTTING

  r[n+1]

  r[0] = 0

  for j = i to n

    maximum_revenue = -INF

    for i in 1 to j

      maximum_revenue = max(maximum_revenue, c[i] + r[j-i])

    r[j] = maximum_revenue

  return r[n]

C - code

INF = 100000;

r = [0] + [-1*INF]*5

def max(x, y):

  if x > y:

    return x

  return y

def bottom_up_rod_cutting(c, n):

  r = [0]*(n+1)

  r[0] = 0

  for j in range(1, n+1):

    maximum_revenue = -1*INF

    for i in range(1, j+1):

      maximum_revenue = max(maximum_revenue, c[i] + r[j-i])

    r[j] = maximum_revenue

  return r[n]

if __name__ == '__main__':

  #array starting from 1, element at index 0 is fake

  c = [0, 10, 24, 30, 40, 45]

  print(bottom_up_rod_cutting(c, 5))

The analysis of the bottom up code is simple. We are using nested loops, the first loop is iterating from 1 to n and the second loop is iterating from 1 to j (j ranging from 1 to n). So, it will result in Θ(n2) time. You can do the full analysis yourself if you are not convinced or can read the Analyze Your Algorithm chapter to see the examples of analysis of algorithms. You can even raise a doubt in the discussion section and find help from other members. The top-down approach also gives us a Θ(n2) running time.

Among the algorithms we studied so far, you can see that our first task was to come up with a solution for the problem and then we were focusing on making a code for it and this is what one should do while dealing with an unknown problem that is, focus on finding a solution for the problem first.

This is the solution for the given problem , this solution is as per my knowledge. I hope you accept this as solution for the given question.