Develop a c++ program for the cut-rod problem: Given a rod of length n inches an
ID: 3678973 • Letter: D
Question
Develop a c++ program for the cut-rod problem:
Given a rod of length n inches and a table of prices pi for i = 1, 2, ...,n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces. Note that if the price pn for a rod of length n is large enough, an optimal solution may require no cutting at all.
Your program must output the running time for rod-lengths of 1 to 40.
Include the running-time behavior, expressed as Big-O.
Requirements:
1.) Code that displays the optimal revenue for lengths 1 to 40
2.) For each length, the code must display the run-time for the algorithm (note: I am not interested in run-time for the entire program, only the cut-rod algorithm). Your output should be a table with n, optimal revenue, run-time.
Example:
n | optimal revenue | run-time
1 1 10
2 5 100
... ... ...
4 10 950
... ... ...
3.) An expression of the behavior in terms of Big-O. PROVIDE PROOF/EXPLANATION
p[11] to p[40] = 30
Explanation / Answer
var priceData = {1: 1};
var revenues = { 0: 0};
var pieces = [];
var rod_length = process.argv[2];
if (rod_length == undefined || rod_length > 10)
{
console.log("Provide rod_length");
return;
}
for (var i = 1; i <= rod_length; i++)
{
var revenue = -1;
for (var smallPieceLength = 1; smallPieceLength <= i; smallPieceLength++)
{
if (revenue != -1 && revenue < (priceData[smallPieceLength] + revenues[i - smallPieceLength]))
{
pieces = [];
pieces.push(smallPieceLength);
(i - smallPieceLength) > 0 ? pieces.push(i - smallPieceLength) : false;
}
revenue = Math.max(revenue, priceData[smallPieceLength] + revenues[i - smallPieceLength]);
};
revenues[i] = revenue;
};
console.log("Maximum revenue from rod of length " + rod_length + " is " + revenues[rod_length] + " with pieces cut as " + JSON.stringify(pieces));
Complexity is Big O(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.