fork download
copy 
  1. /**
  2.  * Coin Change Problem
  3.  * @author r.prateek
  4.  *
  5.  */
  6.  class CoinChange {
  7. 	static int[] coins = { 30 ,24 , 12 , 6 , 3 , 1 };
  8. 	static int W = 53 ;
  9.  
  10. 	/*static int[] coins = { 1 , 2 , 5 };
  11. 	static int W = 7 ;*/
  12.  
  13.  
  14. 	public static void main(String[] args) {
  15.  
  16. 		CoinChange obj=new CoinChange();
  17. 		obj.coinChange(coins, 1);
  18. 		System.out.println("Minimum Coins Required : " + fValues[W]);
  19. 		System.out.println("Coin denomindations required are :");
  20. 		obj.print(W);
  21. 	}
  22.  
  23. 	static int index=0;
  24. 	static int [] S = new int[W + 1];
  25. 	static int[] fValues= new int[W+1] ;
  26.  
  27. 	public void coinChange(int[] coins , int w){
  28.  
  29. 		if(w > W)
  30. 			return ;
  31.  
  32. 		int min=w , fValue , coin = 0;
  33.  
  34. 		for(int i=0;i<coins.length ;i++) {
  35. 			if(w >= coins[i]) {
  36.  
  37. 				fValue = fValues[w-coins[i]] ;
  38.  
  39. 				if(min > fValue)
  40. 				{
  41. 					min = fValue;
  42. 					coin=i;
  43. 				}
  44. 			}
  45. 		}
  46. 		fValues[++index] = min +1 ;
  47.  
  48. 		S[w] = coin ;
  49. 		coinChange(coins , w + 1);
  50. 	}
  51.  
  52. 	public void print(int W ){
  53. 		while(W>0)		{
  54. 			System.out.print(coins[S[W]] + "\t");
  55. 			W=W-coins[S[W]];
  56. 		}
  57. 	}
  58. }
  59.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum Coins Required : 5
Coin denomindations required are :
24	24	3	1	1
https://ideone.com/qwf3Ki
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!