fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. import java.util.Arrays;
  8.  
  9.  class Ideone {
  10.  
  11. 	static int max = 0;
  12.  
  13. 	public static void main(String[] args) {
  14. 		// TODO Auto-generated method stub
  15. 		Random rand = new Random();
  16. 		for(int N=1; N<=50; N++) {
  17.  
  18. 			int [] elem = new int[N];
  19. 			for(int i=1; i<=N; i++) {
  20. 				elem[i-1] = rand.nextInt(999)+1;
  21. 			}
  22. 			max = 0;
  23. 			//System.out.println(Arrays.toString(elem));
  24. 			long start = System.currentTimeMillis();
  25.  
  26. 			int maxHeight = getMaxHeight(elem);
  27.  
  28. 			long end = System.currentTimeMillis();
  29. 			System.out.println(N+"==>"+maxHeight +" Time Taken="+(end-start)/1000+"\n\n");
  30.  
  31. 		}
  32.  
  33. 	}
  34.  
  35. 	private static int getMaxHeight(int[] elem) {
  36. 		// TODO Auto-generated method stub
  37.  
  38. 		boolean [] table = new boolean[elem.length];
  39.  
  40. 		int sum = 0;
  41.  
  42. 		int [] sumTable = new int[elem.length];
  43.  
  44. 		for(int i=0;i<elem.length; i++) {
  45. 			sum += elem[i];
  46. 			sumTable[i] = sum;
  47. 		}
  48.  
  49.  
  50. 		int max = getMaxComb(elem,0,0,sum/2,table,sumTable);
  51.  
  52. 		return max;
  53. 	}
  54.  
  55. 	private static int getMaxComb(int[] arr, int start, int sum, int half, boolean[] table, int [] sumTable) {
  56. 		// TODO Auto-generated method stub
  57.  
  58. 		if(start==arr.length || sum>half || (sum+sumTable[start])< max ) {
  59.  
  60. 		 if(sum<=half && sum>max && isOtherSumPossible(arr,sum,table)) {
  61. 			 return sum;
  62. 		 }
  63.  
  64. 		  return 0;
  65. 		}
  66.  
  67.  
  68.  
  69. 		table[start] = true;
  70.  
  71. 		int x = getMaxComb( arr , start+1, arr[start]+sum, half,table, sumTable);
  72.  
  73. 		if(max<x)
  74. 			max = x;
  75.  
  76. 		table[start] = false;
  77.  
  78. 		int y = getMaxComb( arr,  start+1,  sum, half,table, sumTable);
  79.  
  80. 		if(max<y)
  81. 			max = y;
  82.  
  83. 		return x>y?x:y;
  84. 	}
  85.  
  86. 	private static boolean isOtherSumPossible(int[] arr, int sum, boolean [] table) {
  87. 		// TODO Auto-generated method stub
  88.  
  89.  
  90. 		if(sum == 0 || arr.length == 0)
  91. 			return true;
  92.  
  93.  
  94. 		int count = 0;
  95. 		for(boolean x : table) {
  96.  
  97. 			count = x==false?count+1:count;
  98. 		}
  99.  
  100. 		int [] data = new int[count+1];
  101.  
  102. 		for(int i=0, j=1; i<arr.length; i++) {
  103.  
  104. 			if(!table[i]) {
  105. 		    	data[j]=arr[i];
  106. 		    	j++;
  107. 		    }
  108.  
  109. 		}
  110.  
  111.  
  112.  
  113. 		boolean [][] dp = new boolean[data.length][sum+1];
  114. 		for(int i=0; i<dp.length; i++) {
  115. 			dp[i][0]=true;
  116. 		}
  117.  
  118. 		for(int i=1; i<dp.length; i++) {
  119.  
  120. 			for(int j=1; j<dp[0].length; j++) {
  121.  
  122. 				if(j<data[i]) {
  123.  
  124. 					dp[i][j] = dp[i-1][j];
  125.  
  126. 				}else {
  127.  
  128. 					dp[i][j] = dp[i-1][j-data[i]];
  129. 				}	
  130. 			}	
  131. 		}
  132.  
  133. 		return dp[dp.length-1][dp[0].length-1];
  134. 	}
  135.  
  136. }
Time limit exceeded #stdin #stdout 5s 2317312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1==>0 Time Taken=0


2==>0 Time Taken=0


3==>0 Time Taken=0


4==>0 Time Taken=0


5==>0 Time Taken=0


6==>0 Time Taken=0


7==>0 Time Taken=0


8==>0 Time Taken=0


9==>2123 Time Taken=0


10==>1616 Time Taken=0


11==>2451 Time Taken=0


12==>2932 Time Taken=0


13==>1717 Time Taken=0


14==>2567 Time Taken=0


15==>3465 Time Taken=0


16==>3212 Time Taken=0


17==>5045 Time Taken=0


18==>4837 Time Taken=0


19==>5504 Time Taken=0


20==>4938 Time Taken=0


21==>4757 Time Taken=0


22==>6094 Time Taken=0


23==>4901 Time Taken=1


24==>5363 Time Taken=0


25==>5651 Time Taken=0


26==>7104 Time Taken=0


27==>6145 Time Taken=0


28==>6503 Time Taken=0
https://ideone.com/cAbe4g
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

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!