fork(9) download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <sys/time.h>
  4. #include <limits.h>
  5.  
  6. using namespace std;
  7.  
  8. int max2(int a, int b)
  9. {
  10. 	return (a>b) ? a : b;
  11. }
  12.  
  13. int max3(int a, int b, int c)
  14. {
  15. 	if(a>c)
  16. 		return (a>b) ? a : b;
  17. 	else
  18. 		return (c>b) ? c : b;
  19. }
  20.  
  21. int min3(int a, int b, int c)
  22. {
  23. 	if(a<c)
  24. 		return (a<b) ? a : b;
  25. 	else
  26. 		return (c<b) ? c : b;
  27. }
  28.  
  29.  
  30. int Coins_rec(int * S, int m, int n)
  31. {
  32. 	if(n == 0)
  33. 		return 1;
  34.  
  35. 	if(n < 0)
  36. 		return 0;
  37.  
  38. 	if(m<=0 && n >=0){
  39. 		return 0;
  40. 	}
  41.  
  42. 	return ( Coins_rec( S, m-1, n ) + Coins_rec( S, m, n - S[m-1] ) );
  43. }
  44.  
  45.  
  46. int memo[101][101] ;
  47.  
  48.  
  49. int Coins_memoization(int * S, int m, int n)
  50. {
  51.  
  52. 	if(n == 0)
  53. 		return 1;
  54.  
  55. 	if(n < 0)
  56. 		return 0;
  57.  
  58. 	if(m<=0 && n >=0){
  59. 		return 0;
  60. 	}
  61.  
  62. 	if(memo[m][n] !=-1) {
  63.  
  64. 		return memo[m][n];
  65. 	} else
  66. 	{
  67. 		memo[m][n] = ( Coins_memoization( S, m-1, n ) + Coins_memoization( S, m, n - S[m-1] ) );
  68. 		return memo[m][n];
  69. 	}
  70.  
  71. }
  72.  
  73.  
  74. int Coins_tabulation (int * S, int m, int n)
  75. {
  76. 	int L[m+1][n+1] ;	//L[i][j] -> Minimum number of 'i' different types of coins required to make final amonut j
  77. 	int i, j;
  78.  
  79. 	L[0][0] = 1;
  80.  
  81. 	for(i=0;i<=m;i++){
  82. 		for(j=0;j<=n;j++){
  83. 			if (i == 0 && j >= 0) {
  84. 				L[0][j] = 0;
  85. 			} else if (i > 0 && j == 0) {
  86. 				L[i][0] = 1;
  87. 			} else {
  88. 				L[i][j] = ( (i >= 1) ? L[i-1][j] : 0 ) + ( (j - S[i-1] >=0) ? L[i][j - S[i-1]] : 0 ) ;
  89. 			}
  90. 		}
  91. 	}
  92. 	return L[m][n];
  93. }		// -----  end of function Coins_tabulation  ----- 
  94.  
  95.  
  96.  
  97.  
  98. int main() {
  99.  
  100. 	int arr[] = {2, 5, 3, 6};
  101. 	int m = sizeof(arr)/sizeof(arr[0]);
  102. 	int n;
  103.  
  104. 	cout << "Enter the amount" << endl;
  105. 	cin >> n;
  106.  
  107. 	for(int i=0; i<=101; i++){
  108. 		for(int j=0; j<=101; j++){
  109. 			memo[i][j] = -1;
  110. 		}
  111. 	}
  112.  
  113. 	struct timeval t0; gettimeofday(&t0 , NULL);
  114.  
  115. 	cout << "Number of Ways = " << Coins_rec(arr, m, n) << endl;
  116. 	struct timeval t1; gettimeofday(&t1 , NULL);
  117. 	cout << "-------------- recursion : " << (t1.tv_sec - t0.tv_sec) << " seconds and " << (t1.tv_usec - t0.tv_usec) << " microseconds" << endl;
  118.  
  119. 	cout << "Number of Ways (Memoization) = "  << Coins_memoization(arr, m, n) << endl;
  120. 	struct timeval t2; gettimeofday(&t2 , NULL);
  121. 	cout << "-------------- memoization : " << (t2.tv_sec - t1.tv_sec) << " seconds and " << (t2.tv_usec - t1.tv_usec) << " microseconds" << endl;
  122.  
  123.  
  124. 	cout << "Number of Ways (Tabulation) = "  << Coins_tabulation(arr, m, n) << endl;
  125. 	struct timeval t3; gettimeofday(&t3 , NULL);
  126. 	cout << "-------------- tabulation : " << (t3.tv_sec - t2.tv_sec) << " seconds and " << (t3.tv_usec - t2.tv_usec) << " microseconds" << endl;
  127.  
  128. 	return 0;
  129.  
  130. }
Time limit exceeded #stdin #stdout 5s 3504KB
comments (?)
stdin
copy 
10000
stdout
copy 
Enter the amount
https://ideone.com/14bBIv
language:
C++14 (gcc 8.3)
created:
10 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!