Rod Cutting Problem: Given a rod of length 20 meters and an array of prices that...

 

Transcribed Image Text:

Rod Cutting Problem: Given a rod of length 20 meters and an array of prices that includes prices of all pieces of sizes (See Table 1). Determine the maximum revenue obtainable by cutting up the rod and selling the pieces. Table 1: Price Table Lengths 11 12 13 14 15 Lengths 1m 2m 3m 4m 5m Prices $1 $5 Does this problem have an optimal substructure? If so, explain why using three conditions that need to satisfy to capture the optimal substructure of the problem. (See three conditions in the course slide) $8 $9 $9 Write the recurrence function for the given problem. till each array out with your solutions. Give a memorization table and solution table for the given problem and submit.cpp file in the blackboard. Use dynamic programming to solve the given problem. Use C++ and Rod Cutting Problem: Given a rod of length 20 meters and an array of prices that includes prices of all pieces of sizes (See Table 1). Determine the maximum revenue obtainable by cutting up the rod and selling the pieces. Table 1: Price Table Lengths 11 12 13 14 15 Lengths 1m 2m 3m 4m 5m Prices $1 $5 Does this problem have an optimal substructure? If so, explain why using three conditions that need to satisfy to capture the optimal substructure of the problem. (See three conditions in the course slide) $8 $9 $9 Write the recurrence function for the given problem. till each array out with your solutions. Give a memorization table and solution table for the given problem and submit.cpp file in the blackboard. Use dynamic programming to solve the given problem. Use C++ and