CareerCup

public class Min_Coin_DP {
	
public static int Min_Coin(int []s,int sum)
{
	int [] min_coins= new int[sum+1];
	min_coins[0]=0;
	
	for(int i=1;i<min_coins.length;i++)
		min_coins[i]=Integer.MAX_VALUE;
	
	for(int i=1;i<=sum;i++)
		for(int j=0;j<s.length;j++)
			if((s[j]<=i) && (min_coins[i-s[j]]+1<min_coins[i]))
				min_coins[i]=min_coins[i-s[j]]+1;
	
	
	return min_coins[sum];
}


public static void main(String args[])
{
	Scanner in = new Scanner(System.in);
		int sum,n;
	System.out.println("Enter the number of coins you have:");
	n=in.nextInt();
int [] coins= new int[n];	
System.out.println("\nEnter the coins you have:");
	for(int i=0;i<n;i++)
		coins[i]=in.nextInt();
    System.out.println("\nEnter the Value to get change:");
    sum=in.nextInt();
    System.out.println("\nThe minimum number of coins required for a change of "+sum+" is :"+Min_Coin(coins,sum));
    

}



}

Say, we know the number of coins required for n-1, we can extend it for n also.
1. Take a minCount array. If minCount[i]==j, then minimum of j number of coins are required for i.

void countCoins(int* coin,int size,int tofind)
{
        int minCount[tofind+1],i,j,mintillnow;
 
        for(i=0;i<tofind+1;++i)
                minCount[i]=0;
 
        for(i=0;i<size;i++)
                if(coin[i]<=tofind)
                        minCount[coin[i]]=1;
        for(i=1;i<=tofind;i++)
        {
                if(!minCount[i])
                {
                        mintillnow=INT_MAX;
                        for(j=1;j<i;++j)
                        {
                                if(minCount[j]+minCount[i-j]<mintillnow)
                                        mintillnow=minCount[j]+minCount[i-j];
                        }
                        minCount[i]=mintillnow;
                }
        }
        printf("Minimum number of coins needed is: %d",minCount[tofind]);
}

The only disadvantage of this method is that it may require large amount of space.
e.g. we may need change of Rs 1 lakh[space required is 1lakh bytes]. However, it can be reduced if we go for bit-vector.

Complete code here: ideone.com/pKEwC

implemented the following algo
ccs. neu. edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf

#include <stdio.h>

void coinchange(int coin[], int num, int sum)
{
	int i, j;
	int *C;
	int min;
	
	C = (int*)malloc((sum+1)*sizeof(int));
	C[0] = 0;
	
	for (i=1; i <= sum; i++)
	{
		min = 999;
		for (j = 0; j<num; j++)
		{
			if (coin[j] <= i)
			{
				if (min > C[i-coin[j]]+1)
				{
					min = C[i-coin[j]]+1;
				}
			}
		}
		C[i] = min;
	}
	
	printf("minimum coins required %d", C[sum]);
}

int main()
{
	int coin[] = {1,2,5};
	coinchange(coin, 3 ,9);
}

Greedy is not OK in this problem. Simple search "greedy coin change algorithm" and wiki will tell you greedy is not guaranteed to give you optimal solution. Refer to other posts for counter-examples.
Always keep in mind that set sum problem is a NPC problem. All the DP algorithm posted here are psuedo-polynomial time solutions since when the number of bits used to represent target value increases, the time-space complexity increases exponentially. For more details, also google "set sum problem pseudo polinomial".
Coin-change problem, also known as knapsack problem, is frequently tested. A brute force method is always a good start.
Since we have unlimited number of each denomination coin, given a target value, and current coin we are considering, we can convert this problem to "how many coins that have equal value to the current coins can we take before we study the next coin", and the value ranges from 0 to target/current coin value. Now we have the following code:

int brutehelper(vector<int>& cand, int target, int i) {
	int ret = INT_MAX;
	if (target == 0) return 0;
	if (target < 0 || i < 0) return -1;
	for (int repeat = 0; repeat <= target / cand[i]; ++repeat) {
		int subproblem = brutehelper(cand, target - repeat*cand[i], i - 1);
		if (subproblem < 0) continue;
		ret = min(ret, subproblem + repeat);
	}
	return (ret == INT_MAX) ? -1: ret;
}

If we think this problem in another way, that is, for the current coin, we either consider it as part of the target value, or we exclude it from the target value, and we will have another brute force version:

int brutehelper2(vector<int> &cand, int target, int i) {
	if (target == 0) return 0;
	if (target < 0 || i < 0) return -1;
	int cand1 = brutehelper2(cand, target, i - 1);		// don't keep current
	int cand2 = brutehelper2(cand, target - cand[i], i);// keep current
	if (cand2 >= 0) cand2 += 1;
	if (cand1 < 0) return cand2;
	if (cand2 < 0) return cand1;
	return min(cand1, cand2);
}

It is easy to see that subproblems are overlapping, with some memoization, the second brute force method can be easily converted to top-down DP solution:

int dphelper(vector<int> &cand, int target, int i, vector<vector<int>>& memo) {
	if (target == 0) return 0;
	if (target < 0 || i < 0) return -1;
	if (memo[target][i] != 0) return memo[target][i];
	int cand1 = dphelper(cand, target, i - 1, memo); 
	int cand2 = dphelper(cand, target - cand[i], i, memo);
	if (cand2 >= 0) ++cand2;
	if (cand1 < 0) memo[target][i] = cand2;
	else if (cand2 < 0) memo[target][i] = cand1;
	else memo[target][i] = min(cand1, cand2);
	return memo[target][i];
}

On the other hand, the first brute force method is ideal when constructing bottom-up DP solution:

int bottomUpDp(vector<int>& cand, int target) {
	if (target == 0) return 0;
	if (target < 0 || !cand.size()) return -1;
	vector<vector<int>> memo(cand.size(), vector<int>(target+1, 0));
	for (int val = 0; val <= target; ++val) {
		memo[0][val] = val%cand[0] ? -1 : (val / cand[0]);
	}
	for (int i = 1; i < cand.size(); ++i) {
		for (int val = 1; val <= target; ++val) {	// the immediate value of target
			int tmp = INT_MAX;
			for (int repeat = 0; repeat <= val / cand[i]; ++repeat) {
				if (memo[i - 1][val - repeat*cand[i]] < 0) continue;
				tmp = min(tmp, memo[i - 1][val - repeat*cand[i]] + repeat);
			}
			memo[i][val] = (tmp == INT_MAX) ? -1 : tmp;
		}
	}
	return memo[cand.size() - 1][target];
}

More on knapsack problem, DP memory optimization can be found at

love-oriented.com/pack/

. Playable version for the above four methods can be found at:

ideone.com/KQ2lhU

// Here is another easy to code solution :)

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int coins[101];
int C(int sum,int m)
{   if(m==0 && sum>0) return sum/coins[0];   
    if(sum==0) return 0;
    if(sum<coins[m])
           return C(sum,m-1);
    else        
           return min(C(sum,m-1),C(sum-coins[m],m)+1);
}
main()
{   int n,i,amt;
    scanf("%d",&n);
    for(i=0;i<n;i++)  scanf("%d",coins+i);
    
    scanf("%d",&amt);
    printf("min coins required are : %d\n",C(amt,n-1));
    return 0;
}

c(sum,n) = c(sum,n-1)+c(sum-d[n],n)

package programs;
import java.util.Scanner;


public class Main {

    static int[] denom;
    static int[] memory;
    
    public static int minChange(int x)
    {
        int min = Integer.MAX_VALUE;
        if(x == 0) return 0;
        if(memory[x] != 0) return memory[x];
        for(int i=0;i<denom.length;i++)
        {
           int temp = 0;
           if(x-denom[i]>=0)
           {   if(x-denom[i]== 0) 
                   temp = 1;
               else
               {
                   if(memory[x-denom[i]]!=0) 
                       temp = memory[x-denom[i]]+ 1;
                   else
                       temp = minChange(x-denom[i])+ 1;
               }
           }
           else
               break;
           if(min>temp)min=temp;
        }
        return min;
    }
    public static void main(String[] args)
    {
        int n;
        int amount;
        Scanner in = new Scanner(System.in);
        System.out.println("Please enter the nuber of denom: ");
        n = in.nextInt();
        denom = new int[n];
        System.out.print("Enter the values of denoms in ascending order: ");
        for (int i=0; i<n;i++)
        {
            denom[i] = in.nextInt();
        }
       System.out.println("Enter the total to make change: ");
        amount = in.nextInt();
        memory = new int[amount+1];
        for (int i=0;i<=amount;i++)
            memory[amount]=0;
        for (int i=0;i<denom.length;i++)
            memory[denom[i]] = 1;
        System.out.println("The minimum amount of coins required is "+ minChange(amount));
    }

}

function [n,usage]=coinChange(set, total)

for v=1:total
    min=v;
    for i=1:length(set)
        if (set(i)<=v)
            if(set(i)<v)
                temp=usage(v-set(i))+1;    
            elseif (set(i)==v)
                temp=1;
            end
            if (temp<min)
                min=temp;
            end    
        end
       
    end
    usage(v)=min;
    
end
n=usage(total);

DP in matlab

function [n,usage]=coinChange(set, total)

for v=1:total
    min=v;
    for i=1:length(set)
        if (set(i)<=v)
            if(set(i)<v)
                temp=usage(v-set(i))+1;    
            elseif (set(i)==v)
                temp=1;
            end
            if (temp<min)
                min=temp;
            end    
        end
       
    end
    usage(v)=min;
    
end
n=usage(total);

#include<stdio.h>
#include<conio.h>
int coins[101];
int coinc(int ,int );
void main(){
int n=0,x=0,i=0,amt=0;
printf("no of coins");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&coins[i]);
printf("enter the amount");
scanf("%d",&amt);
x=coinc(amt,n-1);
printf("%d",x);
getch();
}
int coinc(int sum,int n)
{
if(sum >= coins[n])
{
return(1 + coinc(sum-n,n));
}
else if(sum < coins[n])
{
return(coinc(sum,n-1));
}
else if(n==0)
{
if(sum>0 && sum%coins[n]==0)return(sum/coins[0]);
}
else if(sum==0)
{
return 0;
}
else
{
return 0;
}

}

Not necessarily DP!!!

A simple C++ implementation.

#include<iostream>
#include<limits.h>
#include<string.h>
using namespace std;
int exchange( int arr[] , int num , int n ) {
	int flag=0 , min , dp[100] ;
	memset ( dp , 0 , sizeof ( dp ) ) ;

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

	for( int i = 1 ; i <= num ; i++ ){
		min = INT_MAX;
		if( dp [ i ] == 0 ){
			for( int j = 0 ; j < n ; j++ ){
				int current = ( i - arr[ j ] ) > 0 ? 1 + dp [ i - arr [ j ] ] : ( INT_MAX / 2 );
				if( current < min )
					min = current;
				}
		dp[ i ] = min;	
			}
		}
	return dp [ num ];
	}
int main(){

int arr[ ] = { 4 , 3 , 7 };
int c = 15;
int n = sizeof ( arr ) / sizeof ( arr [ 0 ] );
cout<< exchange( arr , c , n ) << endl;
return 0;

	}

#!/usr/bin/python

ds = [25, 10, 5, 2, 1]
s = 45
minc = [-1] * (s+1)
minc[0] = 0

for i in range(1, s + 1):
    h = s + 1
    for d in ds:
        if i >= d:
            if minc[i-d] >= 0:
                if h > minc[i-d]:
                    h = minc[i-d]
    if h > s:
        h = -1;
    minc[i] = h + 1

print minc[s]

below solution is based on DP

public class Coins {

    public static void main(String[] args){

        int[] denom=new int[]{1,2,3};

        int amount=10;
        int min=999;

        int[] minCount=new int[amount+1];

       for(int i=1;i<=amount;i++)
           for(int j=0;j<denom.length;j++){

               if(i>=denom[j] && min>minCount[i-denom[j]]){
                   minCount[i]=minCount[i-denom[j]]+1;
               }
           }


             System.out.println(minCount[amount]);
    }
}

import java.util.Arrays;
public class LowCoinDenom {
	public static int findCoins(int[] denominations,int sum)
	{
		int[] a = new int[sum + 1];
				Arrays.fill(a, Integer.MAX_VALUE-1);
				a[0]=0;
				for (int i = 0; i <= denominations.length-1; i++) 
							for (int j = denominations[i]; j <= sum; j++) 
									a[j] = Math.min(1 + a[j - denominations[i]], a[j]);				
		return a[sum];
		}
	public static void main (String[] args ) {
		int [] coins ={1,2};
		int den=9;
		System.out.println(findCoins(coins,den));
	}
}

#include<stdio.h>
int count (int s[],int m, int n)
{ //Checking the base cases
if (n==0)
return 1;
if(n<0)
return 0;
if(m<=0&&n>=1)
return 0;
return count(s,m-1,n)+count(s,m,n-s[m-1]);
}
int main()
{
int i,j;
int arr[50]={};
int m=sizeof(arr)/sizeof(arr[0]);
printf ("%d",count(arr,i,j);
getch ();
return 0;
}

It is still nearer to O(n) than O(n^2) where n is the number of types of denomination

Example: for denomination:{1,2,4,5,6} output:2 {denomination: 5,4}

package com.programs;
import java.util.Scanner;
public class CoinProblem {
	/**
	 * Minimum Coin Problem
	 */
	static int[] coin = {1,2,4,5,6};
	
	static int getMinCoins(int total_amount)
	{
		int min_coin = 0,temp =0,opti_min_coin=9999999,temp_amount;
	   for(int  i = coin.length-1;i>=0;i--)
	   {
		   min_coin=0;
		   temp_amount = total_amount;
		for(int j= i;j>=0;j--)
		{
			temp = temp_amount/coin[j];
			temp_amount = temp_amount - temp*coin[j];
			min_coin+=temp;
			if(total_amount==0 || min_coin > opti_min_coin)
				break;
		}		
		opti_min_coin=(min_coin < opti_min_coin)?min_coin:opti_min_coin;
	   }
		return opti_min_coin;
	}
	public static void main(String[] args) {
				 
		int total_amount, min_num_coins;
		
		//getting the value of the amount
		System.out.println("Enter the amount:");
		Scanner scanner = new Scanner(System.in);
		total_amount = scanner.nextInt();
		min_num_coins = getMinCoins(total_amount);
		System.out.println(min_num_coins);
	}
}

I prefer to say this is greedy problem.
public int minCoin(int[] coins, int sum){
Arrays.sort(coins);
int res = 0;
for(int i=coins.length-1;i>=0;i--){
if(sum==0){
return res;
}
int pro=sum/coins[i];
res+=pro;
sum-=pro*coins[i];
}
return res;
}