Develop a program for the cut-rod problem. Your program must output the running
ID: 3678892 • Letter: D
Question
Develop a program for the cut-rod problem.
Your program must output the running time for rod-lengths of 1 to 40. You must also include the running-time behavior, expressed as Big-Oh, with your submission.
Submission Requirements:
1.) Functional 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.
For 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-Oh. You MUST PROVIDE PROOF/EXPLANATION
Your submission must include the aforementioned 3 items, which MUST be in 3 different documents
(e.g., .java file, text file that displays the output, and a text file that displays the Big-Oh with your explanation).
NOTE: p[11] to p[40] = 30
Explanation / Answer
Logic for cut-rod algorithm:
public static int profit(int[] value, int length) {
if (length <= 0)
return 0;
// either we will cut it or don't cut it
int max = -1;
for(int i=0;i<length;i++)
max = Math.max(max, value[i] + profit(value, length-(i+1)));
return max;
}
Code for the cut-rod algorithm:
public class RodCutting {
public static int profitDP(int[] value, int length) {
int[] solution = new int[length + 1];
solution[0] = 0;
for (int i = 1; i <= length; i++) {
int max = -1;
for (int j = 0; j < i; j++) {
//obtaining optimum value
max = Math.max(max, value[j] + solution[i - (j + 1)]);
solution[i] = max;
}
}
return solution[length];
}
public static void main(String[] args) {
int[] value = { 2, 3, 7, 8, 9 };
int len = 5;
System.out.println("Max profit for length is " + len + ":"
+ profitDP(value, len));
}
}
public static int profit(int[] value, int length) {
if (length <= 0)
return 0;
// either we will cut it or don't cut it
int max = -1;
for(int i=0;i<length;i++)
max = Math.max(max, value[i] + profit(value, length-(i+1)));
return max;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.