I have some amount given say 230. Now I have to find the minimum number of coins of 100, 50 and 20 so I can make a sum of 230.

Here is my Java code, here I tried with greedy logic but it fails:

public List<Integer> getCoins(int amount) {
   int a = amount /100;
   int bal = amount % 100;
   int b = bal/ 50;
   bal %= 50;
   int c = bal/20;
   List<Integer> list = Arrays.asList(a,b,c);
  return list;
}

My program gives a wrong answer as [2,0,1] but the correct one is [1,1,4] Similarly for input 60 the correct output is [0,0,3]

What is the correct approach to solve this task?

CodePudding user response：

I have an answer but unfortunately it uses a cycle. I'll share it with you, although you might prefer something cleaner.

int count20=0;
while(amountP!=0){
  amount-=20;
  count20  ;
}
int a = amount/100
amount%=100;
int b=amount/50;

I'm interested to see if someone found a smarter way to solve this. Bye, have a nice coding session.

CodePudding user response：

This works for me

public int coinChange(int[] coins, int amount) {
    int max = amount   1;             
    int[] dp = new int[amount   1];  
    int[] change = new int[amount   1]; 
    Arrays.fill(dp, max);  
    dp[0] = 0;   
    for (int i = 1; i <= amount;  i  )   {
        for (int j = 0;  j  <  coins.length;  j  )  {
            if (coins[j]  <=  i)  {
                if (dp[i]  >  dp[i - coins[j]]     1)  {
                    change[i]  =  j;
                    dp[i] = dp[i  -  coins[j]]     1;
                }                    
            }
        }
    }
    int cur  =  amount;
    do  {
        System.out.println(coins[change[cur]]);
        cur  -=  coins[change[cur]];
    }
    while (cur  >  0);
   
    return dp[amount] > amount ? -1 : dp[amount];
}

Prints

20, 20, 20, 20, 50, 100