Java: Implement: 1) extended_buttom_up_cut_rod, 2) buttom_up_cut_rod, 3) memoize
ID: 3597432 • Letter: J
Question
Java: Implement:
1) extended_buttom_up_cut_rod, 2) buttom_up_cut_rod, 3) memoized_cut_rod_aux, and 4) memoized_cut_rod. Fill in the blanks remaining code. Please make sure the program works. I use Eclipse.
public class RodCut {
int n;
int[] p;
int[] r;
int[] s;
public RodCut () {
n = 10;
p = new int[11];
p[0] = 0;
p[1] = 1;
p[2] = 5;
p[3] = 8;
p[4] = 9;
p[5] = 10;
p[6] = 17;
p[7] = 17;
p[8] = 20;
p[9] = 24;
p[10] = 30;
}
public int memoized_cut_rod () {
/*
* Fill in
*/
}
public int memoized_cut_rod_aux () {
/*
* Fill in
*/
}
public int bottom_up_cut_rod () {
*/
* Fill in
*/
}
public void extended_bottom_up_cut_rod () {
*/
*Fill in
*/
}
public void print_cut_rod_solution () {
for (int i = 0; i <= n; i++) {
System.out.print(i + " ");
}
System.out.print(" ");
for (int i = 0; i <= n; i++) {
System.out.print(r[i] + " ");
}
System.out.print(" ");
for (int i = 0; i <= n; i++) {
System.out.print(s[i] + " ");
}
System.out.print(" ");
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
RodCut rc;
rc = new RodCut();
System.out.println("memoized_cut_rod starts ------------------");
System.out.println(rc.memoized_cut_rod());
System.out.println("memoized_cut_rod ends ------------------");
System.out.print(" ");
System.out.println("bottom_up_cut_rod starts ------------------");
System.out.println(rc.bottom_up_cut_rod());
System.out.println("bottom_up_cut_rod ends ------------------");
System.out.print(" ");
System.out.println("extended_bottom_up_cut_rod starts ------------------");
rc.extended_bottom_up_cut_rod();
rc.print_cut_rod_solution();
System.out.println("extended_bottom_up_cut_rod ends ------------------");
System.out.print(" ");
}
}
Explanation / Answer
public class RodCut {
int n;
int[] p;
int[] r;
int[] s;
public RodCut () {
n = 10;
p = new int[11];
p[0] = 0;
p[1] = 1;
p[2] = 5;
p[3] = 8;
p[4] = 9;
p[5] = 10;
p[6] = 17;
p[7] = 17;
p[8] = 20;
p[9] = 24;
p[10] = 30;
}
public int memoized_cut_rod (int p[], int n) {
if(n >= p.length){
try {
throw new Exception("rod of length can not grater than the price array length");
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
r = new int[n + 1];
for (int i = 0; i <= n; i++) {
r[i] = Integer.MIN_VALUE;
}
return memoized_cut_rod_aux(p,n,r);
}
public int memoized_cut_rod_aux (int p[], int n, int r[]) {
if(n >= p.length){
try {
throw new Exception("rod of length can not grater than the price array length");
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
int q;
if (r[n] >= 0) {
return r[n];
}
if (n == 0) {
q = 0;
} else {
q = Integer.MIN_VALUE;
for (int j = 1; j <= n; j++) {
q = Math.max(q, (p[j] + memoized_cut_rod_aux(p, n - j, r)));
}
}
r[n] = q;
return q;
}
public int bottom_up_cut_rod (int p[], int n) {
if(n >= p.length ){
try {
throw new Exception("rod of length can not grater than the price array length");
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
r = new int[n + 1];
r[0] = 0;
for (int j = 1; j <= n; j++) {
int q = Integer.MIN_VALUE;
for (int i = 1; i <= j; i++) {
q = Math.max(q, (p[i] + r[j - i]));
}
r[j] = q;
}
return r[n];
}
public void extended_bottom_up_cut_rod (int p[], int n) throws Exception {
if(n >= p.length ){
throw new Exception("rod of length can not grater than the price array length");
}
r = new int[n + 1];
s = new int[n + 1];
r[0] = 0;
for (int j = 1; j <= n; j++) {
int q = Integer.MIN_VALUE;
for (int i = 1; i <= j; i++) {
if (q < (p[i] + r[j - i])) {
q = p[i] + r[j - i];
s[j] = i;
}
} r[j] = q;
}
while (n > 0) {
System.out.print(s[n] + " ");
n = n - s[n];
}
}
public void print_cut_rod_solution () {
for (int i = 0; i <= n; i++) {
System.out.print(i + " ");
}
System.out.print(" ");
/* for (int i = 0; i <= n; i++) {
System.out.print(r[i] + " ");
}*/
System.out.print(" ");
for (int i = 0; i <= n; i++) {
System.out.print(s[i] + " ");
}
System.out.print(" ");
}
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
RodCut rc;
rc = new RodCut();
System.out.println("memoized_cut_rod starts ------------------");
System.out.println(rc.memoized_cut_rod(rc.p, rc.n));
System.out.println("memoized_cut_rod ends ------------------");
System.out.print(" ");
System.out.println("bottom_up_cut_rod starts ------------------");
System.out.println(rc.bottom_up_cut_rod(rc.p, rc.n));
System.out.println("bottom_up_cut_rod ends ------------------");
System.out.print(" ");
System.out.println("extended_bottom_up_cut_rod starts ------------------");
rc.extended_bottom_up_cut_rod(rc.p, rc.n);
rc.print_cut_rod_solution();
System.out.println("extended_bottom_up_cut_rod ends ------------------");
System.out.print(" ");
}
}
/* output;-
memoized_cut_rod starts ------------------
30
memoized_cut_rod ends ------------------
bottom_up_cut_rod starts ------------------
30
bottom_up_cut_rod ends ------------------
extended_bottom_up_cut_rod starts ------------------
10 0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 2 2 6 1 2 3 10
extended_bottom_up_cut_rod ends ------------------
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.