fork(4) download
copy 
  1. /**
  2.  * Rod Cutting Problem using Bottom Up Approach(DP)
  3.  * @author Prateek
  4.  */
  5. class RodCutting {
  6.  
  7. 	private int[] aux;
  8. 	private int[] cost;
  9. 	int sol[];
  10.  
  11. 	public void solve(int[] cost , int len){
  12. 		this.aux = new int[len+1];
  13. 		this.sol = new int[len+1];
  14. 		this.cost= cost;
  15.  
  16. 		int maxCost=bottomUp(cost, len );
  17. 		System.out.println("Maximum Revenue:  "+maxCost);
  18. 		System.out.print("Rod cut of sizes :  ");
  19. 		printSol(len);
  20. 	}
  21.  
  22. 	/**
  23. 	 * Bottom up Approach
  24. 	 * @param cost
  25. 	 * @param len
  26. 	 * @return
  27. 	 */
  28. 	public int bottomUp(int cost[],int len){
  29. 		aux[0] = 0;  //auxillay array
  30. 		int maxCost = 0;
  31.  
  32. 		for(int i=1;i<=len;i++){
  33. 			 maxCost=Integer.MIN_VALUE;
  34.  
  35. 			for(int j=0;j<i;j++)
  36. 				if(maxCost <  cost[j] + aux[(i-1)-j]){
  37. 					maxCost = cost[j] + aux[(i-1)-j];
  38. 					sol[i] = j+1;
  39. 				}
  40.  
  41. 			aux[i]=maxCost;
  42. 		}
  43. 		return maxCost;
  44. 	}
  45.  
  46. 	private void printSol(int len){
  47. 		while(len > 0){
  48. 			System.out.print(sol[len] + "\t");
  49. 			len=len - sol[len];
  50. 		}
  51. 	}
  52.  
  53. 	public static void main(String[] args) {
  54. 		int[] cost = {1, 5 , 7, 9 , 10	, 16 , 18 , 20 , 22 };
  55. 		//int[] cost = { 1 , 5, 8  , 9,  10 , 17 , 17, 20 , 24 ,30 };
  56. 		int len= 8 ;
  57. 		RodCutting obj=new RodCutting();
  58. 		obj.solve(cost, len);
  59. 	}
  60. }
  61.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum Revenue:  21
Rod cut of sizes :  2	6
https://ideone.com/Fy1Utd
language:
Java (12.0.1)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!