Rod Cutting Problem in DSA Typescript - Build from Scratch

Rod Cutting Problem

📖 Scenario: You have a metal rod of a certain length. You want to cut it into smaller pieces to sell. Each piece has a price depending on its length. Your goal is to find the best way to cut the rod to get the most money.

🎯 Goal: Build a program that calculates the maximum money you can get by cutting the rod into pieces using given prices for each length.

📋 What You'll Learn

Create an array called prices with prices for rod lengths 1 to 8.

Create a variable called rodLength with the value 8.

Create a variable called maxRevenue to store the best money you can get.

Use a loop to calculate the best revenue for each rod length from 1 to rodLength.

Print the maximum revenue for the full rod length.

💡 Why This Matters

🌍 Real World

This problem models how to cut raw materials like metal rods or wood to maximize profit in manufacturing or sales.

💼 Career

Understanding this problem helps in roles involving optimization, dynamic programming, and resource management in software development.

1

Create the prices array

Create an array called prices with these exact values: [1, 5, 8, 9, 10, 17, 17, 20] representing prices for rod lengths 1 to 8.

DSA Typescript

# Your code here

Hint

Use const prices = [1, 5, 8, 9, 10, 17, 17, 20]; to create the array.

2

Set the rod length

Create a variable called rodLength and set it to 8.

DSA Typescript

const prices = [1, 5, 8, 9, 10, 17, 17, 20];
# Your code here

Hint

Use const rodLength = 8; to set the rod length.

3

Calculate maximum revenue

Create a variable called maxRevenue as an array of length rodLength + 1 filled with zeros. Then use a for loop with variable i from 1 to rodLength inclusive. Inside it, use another for loop with variable j from 1 to i inclusive. Update maxRevenue[i] with the maximum of its current value and prices[j - 1] + maxRevenue[i - j].

DSA Typescript

const prices = [1, 5, 8, 9, 10, 17, 17, 20];
const rodLength = 8;
# Your code here

Hint

Use two nested loops to fill maxRevenue with the best prices.

4

Print the maximum revenue

Print the value of maxRevenue[rodLength] using console.log.

DSA Typescript

const prices = [1, 5, 8, 9, 10, 17, 17, 20];
const rodLength = 8;
const maxRevenue = new Array(rodLength + 1).fill(0);
for (let i = 1; i <= rodLength; i++) {
    for (let j = 1; j <= i; j++) {
        maxRevenue[i] = Math.max(maxRevenue[i], prices[j - 1] + maxRevenue[i - j]);
    }
}
# Your code here

Hint

Use console.log(maxRevenue[rodLength]); to print the result.