Suppose that you are selling steel rods, and you know rods of different lengths

Question

Suppose that you are selling steel rods, and you know rods of different lengths can be sold for different price, as listed in the table below. To maximize profit, you to consider cutting a long rod Into multiple short pieces. (Cutting is free and all lengths are integral numbers.) For example, for a rod that is 6-feet long, you would want to cut it into two 3-feet long pieces, resulting in a total price of 14 dollars. (If you do not cut, the price is $13; cutting it into 4 times 1-fooc long pieces, the total price would be $6; 3 x 2 foot would give you $12:1 times 2-foot and 1 times 4-feet would be $13, etc.) Design a dynamic programing algorithm to find an optimal cut for a rod of length n, and use your algorithm to find the optimal price for rods with lengths equal to 13, 14, and 15. For full credit, show the recurrence, pseudocode, the dynamic programming table, the optimal value and a cut that can result in the optimal value.

Explanation / Answer

class RodCutting
{
/* Returns the best obtainable price for a rod of
length n and price[] as prices of different pieces */
static int cutRod(int price[],int n)
{
  int val[] = new int[n+1];
  val[0] = 0;

  // Build the table val[] in bottom up manner and return
  // the last entry from the table
  for (int i = 1; i<=n; i++)
  {
   int max_val = Integer.MIN_VALUE;
   for (int j = 0; j < i; j++)
    max_val = Math.max(max_val,
        price[j] + val[i-j-1]);
   val[i] = max_val;
  }

  return val[n];
}

/* Driver program to test above functions */
public static void main(String args[])
{
  int arr[] = new int[] {1, 4, 7, 9, 11, 13, 16, 17};
  int size = arr.length;
  System.out.println("Maximum Obtainable Value is " +
       cutRod(arr, size));
}
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.