CareerCup

Example1 : Coin denomination is 1, 2 and 5 and S = 8. So greedy yields 3 coins (5+1+2) which is correct
Example2: Coin denomination 1, 4, 5 and S=8, Greedy yields 4 coins (5+1+1+1) but the answer is 2 coins (4+4). Hence proves the point.

So DP is the approach we need to follow. Below is the sample code. Just keep an auxiliary array and starting from i=0 we got up to S, each time calculating minimum number of coins needed to get i.

#include<iostream>
using namespace std;
#define INFINITY 10000

int coin_denomination(int *denomination, int d_N, int S);

int main()
{
  int dn;
  cin >> dn;
  int *denomination = new int[dn];
  int x = 0;
  while(x < dn) {
    cin >> denomination[x++];
  }

  int S;
  cin >> S;

  cout << coin_denomination(denomination, dn, S) << endl;
}

int coin_denomination(int *denomination, int d_N, int S) {
  int *aux = new int[S+1];
  for(int i=0; i<denomination[0]; i++) {
    aux[i] = 0;
  }

  aux[denomination[0]] = 1;
  for(int i=1; i<=S ; i++) {
    int min = INFINITY;
    for(int j=0; j< d_N; j++) {
      if(i-denomination[j] >= 0) {
        if((1+aux[i-denomination[j]]) < min) {
          min = (1+aux[i-denomination[j]]);
        }
      }
    }
    aux[i] = min;
  }
 
  return(aux[S]);
}

logic is here:it is O(S) and I doubt it is the same algorithm with the above code
create an array of S elements,call it set,which stores the minimum number of coins,
1.set[0],set[1] unused,set[2]=1,set[3]=1,set[4]=2,set[5]=1,
2.start from k=6,we check
set[k-2],set[k-3],set[k-5],pick the minimum of these three and add it by one and take it as the value of set[k],keep going until we reach S.

pretty easy DP question.

Coin Change Problem

int coins[Sum + 1] = {INT_MAX};
int denominations[Total_Den];

for (int i =1; i <= sum ; i++)
{
   for ( int j = 0 ; j < Total_Den; j++)
   {
       if (i == denominations[j])
	   {
	       coins[i] = 1;
	   }
}

for (int i = 2; i<= sum; i++)
{
   int minSum = a[i];
   int thisSum = INT_MAX;
   for (int j = 1; j < i; j++)
   {
      thisSum = a[j] + a[i - j];
      if (thisSum < minSum)
         minSum = thisSum;	  
   }
   a[i]= thisSum;
}

public class CoinChange {
    
    public static void findChanges(int[] d, int sum) {
        int[] a = new int[sum+1];
        int[] coins = new int[sum+1];
        for (int i=0; i<sum+1; i++) a[i] = 0;
        int total_den = d.length;
        
        for (int i = 1; i<= sum; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < total_den; j++) {
                if (i - d[j] >= 0) {
                    if (1+a[i-d[j]] < min) {
                        min = 1+a[i-d[j]];
                        coins[i] = d[j];
                    }
                }
            }
            a[i] = min;
        }
        while (sum > 0) {
            System.out.print(coins[sum] + ",");
            sum = sum - coins[sum];
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] den = {1, 4, 5, 20};
        findChanges(den, 58);
    }

public static int getMinCoinsForAmt(int denoms[], int amt) {
        if (amt <= 0 || denoms == null || denoms.length == 0) {
            return 0;
        }
        Arrays.sort(denoms); // Not needed if already sorted!
        int dp[] = new int[amt + 1];
        dp[0] = 0;
        for (int i = 1; i <= amt; ++i) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < denoms.length && i >= denoms[j]; ++j) {
                if (dp[i - denoms[j]] != Integer.MAX_VALUE &&
                    min > 1 + dp[i - denoms[j]]) {
                    min = 1 + dp[i - denoms[j]];
                }
            }
            dp[i] = min;
        }
        return (dp[amt] == Integer.MAX_VALUE) ? 0 : dp[amt];
    }

the above code assumes the denoms are 2,3 and 5.

The easiest solution:



int main(){

int coin_Avilabe[]={10,5,2,1};

int total_amount;
int mod=0;
int i=0;
int countOfCoin;
cout<<"please enter the total amount"<<endl;

cin>>total_amount;

while(total_amount){
countOfCoin=total_amount/coin_Avilabe[i];

total_amount=total_amount%coin_Avilabe[i];

if(countOfCoin)
cout<<"number of coin of require of "<<countOfCoin<<":"<<coin_Avilabe[i]<<endl;
i++;
}
}

{{
//dpCount: keeps track of minimum number of coins as the value of key in hashmap
//coins: is a vector of available coins

int nCoins(int S, map<int, int> &dpCount, vector<int> &coins)
{
int retVal = -1;

for (size_t i = 0; i < coins.size(); i++){
if (coins[i] <= S){
int postSum = S-coins[i];

if (dpCount.find(postSum) == dpCount.end()){
dpCount[postSum] = nCoins(postSum, dpCount, coins);
}

if (dpCount.find(S) == dpCount.end()){
dpCount[S] = dpCount[postSum] + 1;
}
else{
dpCount[S] = min(dpCount[S], dpCount[postSum] + 1);
}
}
}

return dpCount[S];
}
}}

{{
//dpCount: keeps track of minimum number of coins as the value of key in hashmap
//coins: is a vector of available coins

int nCoins(int S, map<int, int> &dpCount, vector<int> &coins)
{
	int retVal = -1;

	for (size_t i = 0; i < coins.size(); i++){
		if (coins[i] <= S){
			int postSum = S-coins[i];
			
			if (dpCount.find(postSum) == dpCount.end()){
				dpCount[postSum] = nCoins(postSum, dpCount, coins);
			}

			if (dpCount.find(S) == dpCount.end()){
				dpCount[S] = dpCount[postSum] + 1;
			}
			else{
				dpCount[S] = min(dpCount[S], dpCount[postSum] + 1);
			}
		}
	}

	return dpCount[S];
}

This works fine based on DP and it takes
Time-O(S*D), where S is the sum and D are the number of different denominations
Space-O(S*D)

#include<stdio.h>


int min(int a,int b )
{
   if(a==-1)
	return (b);
	else if(b==0)
	return a;
	else
	return a<b?a:b;

}


int getdenominations(int den[],int n,int sum)
{
int i;
int arr[n+1][sum+1];
for(i=0;i<=sum;i++)
arr[0][i]=0;

for(i=1;i<=n;i++)
arr[i][0]=0;





for(i=1;i<=sum;i++)
{if(i%den[0]==0)
arr[1][i]=i/den[0];
else
arr[1][i]=-1;
}


int j;
	for(i=2;i<=n;i++)
	{
		for(j=1;j<=sum;j++)		//j is the sum
			{
				if(j<den[i-1])
				arr[i][j]=arr[i-1][j];
				else if(j%den[i-1]==0)
				arr[i][j]=j/den[i-1];		//this will be the minimum for this case
				else
				{
				arr[i][j]=min(arr[i-1][j], arr[i][j-den[i-1]]+1);
				}
			}
	}

return arr[n][sum];
}


int main()
{
int den[]={2,3};
int sum=25;
int len=sizeof(den)/sizeof(den[0]);
printf("%d ",getdenominations(den,len,sum) );

return 0;

}