CareerCup

www_youtube_com/watch?v=GafjS0FfAC0


good source for understanding coin change problem

Two approaches in Java. What do you think? They assume the values array will be sorted in increasing order of values. The first approach is a "brute force" one and the second used DP.

public int minimumNumber(int[] values, int sum) {
		int number = 0; 
		int highest = values.length - 1;
		
		while(true) {
			
			if(values[highest] > sum) {
				highest--;
				if(highest < 0) break;
			} else {
			 	if((sum / values[highest]) >= 1) { 
			 		number += (sum/values[highest]);
					sum = sum % values[highest]; 
				}
			} 
		}
		
		return number;
	}
	
	public int minimumNumberDP(int[] values, int sum) { 
		int[] table = new int[sum+1];
		
		for(int i = 0; i < table.length; ++i) {
			table[i] = Integer.MAX_VALUE;    
		}  
		
		table[0] = 0;
		 
		for(int i = 1; i <= sum; ++i) {
			for(int j = 0; j < values.length; ++j) {
				if(values[j] <= i && (table[i - values[j]] + 1 < table[i])) {
					table[i] = table[i - values[j]] + 1;
				}
			}
		}
		
		return table[sum];
	}

#include <iostream>
#include <cstdlib>
bool min_coin (int s, int& try1,int *coin, int nc);
int main (int argc, char * const argv[]) {
   
	int s;
	scanf("%d",&s);
	int nc =6;
    int coin[]={1,2,5,10,20,25};
	int min_c = s;
	int found=0;
	for (int i=0;i<nc;i++)
	{
		int try1;
		if (s-coin[i]>0)
		if (min_coin (s-coin[i], try1,coin, nc))
		{
			if (try1+1<min_c) min_c=try1+1;
			found=1;
		}
	}
	if (!found) std::cout<<"No solution.\n";
	else std::cout<<min_c<<" coins.\n";
    return 0;
}

bool min_coin (int s, int& try1,int *coin, int nc)
{
	//std::cout<<s<<" "<<try1<<"\n";
	for (int i=0;i<nc;i++)
		if (s==coin[i])
		{
			try1=1;
			return true;
		}
	if (s<0) exit(1);
	int min_c=s;
	int found=0;
	for (int i=0;i<nc;i++)
	{
		int try_c;
		if (s-coin[i]>0)
		if (min_coin (s-coin[i], try_c,coin, nc))
		{
			if (try_c+1<min_c) min_c=try_c+1;
			found=1;
		}
		
	}
	if (found)
	{
		try1 = min_c;
		return true;
	}
	return false;
}

Here is the solution using DP

#include <iostream>
#include <cstdlib>


int main (int argc, char * const argv[]) {
   
	int s;
	scanf("%d",&s);
	int nc =6;
    int coin[]={1,2,5,10,20,25};
	int i,j;
	float *max_v=new float [(nc+1)*(s+1)];
    int *min_c = new int [(nc+1)*(s+1)];
	for (i=0;i<=s;i++)
	{
		min_c[0*(s+1)+i] = 0;
		max_v[0*(s+1) + i] = 0.f;
	}
	
	for (i=1;i<=nc;i++)
		for (j=0;j<=s;j++)
		{
			if (j>=coin[i-1])
			{
				int idx_now = i*(s+1)+j;
				int idx_i_1 = (i-1)*(s+1) + j;
				int idx_j_c = i*(s+1) +j -coin[i-1];
				float last_max_v = max_v[idx_j_c];
				int last_min_c = min_c[idx_j_c];
				float new_max_v = last_max_v*(float)last_min_c
				+(float)coin[i-1];
				new_max_v/=(float)(last_min_c+1);
				
				if (new_max_v>max_v[idx_i_1])
				{
					max_v[idx_now]=new_max_v;
					min_c[idx_now]=last_min_c+1;
				}
				else
				{
					max_v[idx_now]=max_v[idx_i_1];
					min_c[idx_now]=min_c[idx_i_1];
				}
				
			}
			else
			{
				int idx_now = i*(s+1)+j;
				int idx_i_1 = (i-1)*(s+1) + j;
				max_v[idx_now]=max_v[idx_i_1];
				min_c[idx_now]=min_c[idx_i_1];
			}
			//show_ij(i,j,s,min_c, max_v);
		}
	float maxv=0.01;
	int max_dx=-1;
	for (i=1;i<=nc;i++)
		if (maxv<max_v[i*(s+1)+s])
		{
			maxv=max_v[i*(s+1)+s];
			max_dx = i;
		}
	if (maxv>0.01)
	{
		std::cout<<min_c[max_dx*(s+1)+s]<<" coins.\n";
	}
	
	delete [] min_c;
	delete [] max_v;
}

public static int getMincoinsnumber(int[] coins,int aim){
Arrays.sort(coins);
int results=compute_posscess(coins,aim,coins.length-1,0,0);
if(results==Integer.MAX_VALUE){
return -1;
}
return results;
}
public static int compute_posscess(int[] coins,int aim,
int index,int currentaim,int currentnumber){
if(index==0){
if(aim==coins[0]+currentaim){
return currentnumber+1;
}
else{
return Integer.MAX_VALUE;
}
}
if(aim==coins[index]+currentaim){
return currentnumber+1;
}
else if(aim<coins[index]+currentaim){
int result=compute_posscess(coins,aim,index-1,currentaim,currentnumber);
return result;
}
else{
int result1=compute_posscess(coins,aim,index-1,currentaim+coins[index],currentnumber+1);
int result2=compute_posscess(coins,aim,index-1,currentaim,currentnumber);
return Math.min(result1, result2);
}
}

Simple start from max denomination coin. And keep subtracting from the sum until sum becomes zero.
C# code for this problem is : Program returning each coin denomination, and count of coin needed to form the sum.

static int[,] MinCoin(int[] coin_den, int sum)
{

int[,] count_each_coin = new int[coin_den.Length, 2];
for (int i = 0; i < coin_den.Length; i++)
{
count_each_coin[i, 0] = coin_den[i];
}

for (int i = 0; i < coin_den.Length; i++)
{
count_each_coin[i, 1] = 0;
}

for (int i = coin_den.Length-1; i >= 0; i--)
{
while (sum - coin_den[i] >= 0)
{
count_each_coin[i, 1] += 1;
sum -= coin_den[i];
}

}

return count_each_coin;
}

/*
* From a set of coins of some value. We find the minimum no. of coins
* required to get count. If not possible returns -1. Done in order O(n^2),
* way better than O(2^n) the brute force approach.
*/
public int getMinCoins(int[] coins, int count) {
int res = -1;
Arrays.sort(coins);
List<Integer> num = new ArrayList<Integer>();
List<Integer> temp = new ArrayList<Integer>();
List<Integer> rep = new ArrayList<Integer>();
for (int i = coins.length - 1; i > -1; i--) {
if (coins[i] == count) {
return 1;
} else if (coins[i] < count) {
for (int j = 0; j < num.size(); j++) {
if (coins[i] + num.get(j) == count) {
return rep.get(j) + 1;
} else if (coins[i] + num.get(j) < count) {
temp.add(coins[i] + num.get(j));
rep.add(rep.get(j) + 1);
// System.out.println("Num : "+(int)(coins[i] +
// num.get(j))+" Rep is : "+(int)(rep.get(j) + 1));
}
}
for (int j = 0; j < temp.size(); j++) {
num.add(temp.get(j));
}
temp.removeAll(temp);
num.add(coins[i]);
rep.add(1);
// System.out.println("Num : "+coins[i] +" Rep is : 1");
}
}
return res;
}

int mincoin(){
int 1c, 5c, 10c, 25c;
1c = 5c = 10c = 25c = 0;
for (int i = 0; i < N; i++){
switch (A[i]){
case penny:
1c++;
break;
case nickel:
5c++;
break;
case dime:
10c++;
break;
case quarter:
25c++;
break;

}
}
int mincoins = 0;
if (S-25*25c < 0){
int diff = 25*25c - S;
return (25c - (int)diff/25);
}
mincoins+=25c;
S-= 25*25c;
if (S-10*10c < 0){
int diff = 10*10c - S;
return (10c - (int)diff/10 + mincoins);
}
mincoins+=10c;
S-= 10*10c;
if (S-5*5c < 0){
int diff = 5*5c - S;
return (5c - (int)diff/5 + mincoins);
}
mincoins+=5c;
S-= 5*5c;
if (S-1*1c < 0){
int diff = 1*1c - S;
return (1c - (int)diff/1 + mincoins);
}
mincoins+=1c;
S-= 1*1c;
if(S > 0){
return -1; //total value of coins is less than S
}
return mincoins;
}

int min_num_coins(const vector<unsigned int>& coins, size_t S) {
  if (S == 0) return 0;
  size_t denominations[] = {25, 10, 5, 1}; // big to small order
  map<size_t, size_t> num_of;
  for (size_t i = 0; i < coins.size(); i++) {
    if (num_of.find(coins[i]) == num_of.end()) 
      num_of[coins[i]] = 1;
    else
      num_of[coins[i]]++;
  }
  unsigned int num_coins = 0;
  for (size_t d = 0; d < 4; d++) {
    size_t k = min(S / denominations[d], num_of[denominations[d]);
    num_coins += k;
    S -= k*denominations[d];
  }
  return num_coins;
}

Here is my DP solution:

int min_num_coins(const vector<size_t>& coins, size_t S) {
  if (S == 0) return 0;
  typedef map<size_t, size_t> NumOfMap;
  NumOfMap num_of;
  for (size_t i = 0; i < coins.size(); i++) {
    if (num_of.find(coins[i]) == num_of.end()) 
      num_of[coins[i]] = 1;
    else
      num_of[coins[i]]++;
  }
  vector<pair<int, NumOfMap> least_coins(S); // least num coins needed for 0 <= i <= S money
  least_coins[0] = make_pair(0, num_of);
  for (int i = 1; i < S; i++) {
    int min_coins = -1;
    size_t min_denom;
    for (NumOfMap::iterator it = num_of.begin(); it != num_of.end(); ++it) {
      size_t denom = it->first;
      if (denom > i) continue;
      int min_sofar = least_coins[i-denom].first;
      NumOfMap& num_of_left = least_coins[i-denom].second;
      if (num_of_left[denom] == 0) continue;
      if (min_sofar + 1 < min_coins) {
        min_coins = min_sofar + 1;
        min_denom = denom;
    }
    if (min_coins < 0) return -1; // Can't find solution
    NumOfMap num_of_left_cpy = least_coins[i-min_denom]; // make a copy
    num_of_left_cpy[min_denom]--;
    least_coins[i] = make_pair(min_coins, num_of_left_cpy);
  }
  return least_coins[S-1].first;
}

void minDiffWork(vector<int> arr, int sum, vector<int> result, int pos)
{
	int i = pos;
	while(i < arr.size() )
	{
		int target = sum - arr[i];
		//sum = sum - arr[i];
		if(i > pos ) 
			result.pop_back();
		result.push_back(arr[i]);
		if(target > 0 )
		{
			//12,4,7,3,1,6,3
			i++;
			minDiffWork(arr, target, result, i);
		}
		else if(target < 0)
		{
			i++;
			continue;
			//break;
		}
		else
		{
			cout << "-----------------------" <<endl;
		    for(int hh = 0; hh <result.size(); hh++)
			   cout << result[hh] << endl;
		    cout << "-----------------------" <<endl;
			break;
		}
	}
}

Best way to solve this is Back Tracking..Plain and simple..Code given above prints all combination, now OP can take it and tweak it for his purpose..

it would be better if people start discussing the approach and algorithms and then paste the sample code.

int min_coin(int coin[], int n, int s)
    {
         int table[n+1];
         table[0]=0;
         for(int i=0;i<n;i++)
            { table[i]=INT_MAX;}
         for(int i=0;i<s;i++)
         {
                int minm=table[i];
                for(int j=0;j<n;j++)
               {      
                      
                      if(i-coin[j]>0)
                      {
                            minmm=min(minm,table[i-s[j]]+1);
                      }
                      
               }
               table[i]=minm;
         }
         return table[n];
         
    }

#include<iostream>
#include<algorithm>
using namespace std;

int minCoins(int *a, int N, int S)
{
	if(S==0)
		return 0;

	int minC = N;
	
	for(int i = 0; i < N; i++)
	{
		if(S-a[i] >= 0)
			minC = min(minCoins(a,N,S-a[i]),minC);
	}
	return minC + 1;
}

int main(void)
{
	const int N = 3;
	int a[N] = {7,7,5};
	int S = 5;
	int minC = minCoins(a,N,S);
	if(minC<=N)
		cout << minCoins(a,N,S) << endl;
	else
		cout << "NOT POSSIBLE" << endl;
}

Sort the array containing values of coins. Take the sum and subtract it from descending order. For the remaining sum after subtraction , perform binary search to rest of the array , if number is found that we have found the Sum with min coins required. If not , continue subtracting and finding the coins

// DP algorithm:
// W is the minimum coins to sum up to sum (s) given coins (c).
// W(s, c) = min (W(s-ci, c-ci)) + 1;


// using C#

// global var. 
// Context has information of current Sum and available coins.
// int is the minimum coin count to satisfy the Context.
// if there is no solution for this context, the context will not be in this hash table.
HashTable<Context, int> T = new HashTable<Context, int>();

class Context
{
    public int s;
    public HashTable<int, int> coins;

    public void Context(int s, int[] arr)
    {
        coins = new HashTable<int, int>();
        foreach(int a in arr)
        {
            if (coins.ContainKey(a))
            {
                coins[a].value++;
            }
            else
            { 
                coins.Add(a, 1);
            }
        }

        this.s = s;
    }

    public void Context(int s, HashTable<int, int> coins)
    {
        this.s = s;
        //TODO: create new HashTable and copy data from coins.        
    }

    // find all available coins whose values is not greater than the sum.
    public List<int> AvailableNotGreater()
    {
        List<int> t = new List<int>();
        foreach(int k in coins.Keys())
        {
            if(k <= s)
            {
               t.Add(k);
            }
        }
        return t;
    }

    // remove a coin from the context.
    public void Remove(int z)
    {
        if(z>s)
            throw new ArgumentException();

        if(!coins.ContainKey(z))
        {
            throw new ArgumentException();
        }

        s-=z;
        if(coins[z]==1)
        {
           coins.Remove(z);
        }
        else
        {
           coins[z]--;
        }         
    }
}

// main function for this question.
// return the minimum coins for the sum (s). return INT_MAX if not found.
int mainfunc(int s, int[] arr)
{
    Context context = new Context(s, arr);

    f(context);

    if(T.ContainKey(context)
    {
        return T[context];
    }
    else
        return INT_MAX;
}

// recursive function using DP
void f(Context context)
{
   if(T.ContainKey[context)
   {
       return;
   }

   foreach(int z in context.AvailableNotGreaterSet())
   {   
       if (z == s)
       {
           if(T.ContainKey(context))
           {
               T[context] = 1;
           }
           else
           {
               T.Add(context,1);
           }
       }
   
       Context contextCopy = new Context(context.s, context.coins);
       contextCopy = contextCopy.Remove(z);

       f(contextCopy);
       if(T.ContainKey(contexCopy))
       {
           int curMin = T[contextCopy]+1;
           if(T.ContainKey(context))
           {
              if(T[context] > curMin)
                  T[context] = curMin;
           }
           else
           {
               T.Add(context, curMin);
           }
       }
   }
}

dp!

for(int i=0;i<sum;i++)
{
	for(int j=0;j<m;j++)
	{

		table[i][j]=table[i][j-1]+ table[i-s[j]][j];
	}

}

I think sorting is not a bad move in this case. I have seen other solutions being downgraded where sorting was involved (probably not because of sorting but because of the actual solution they provided was not correct).

1) Sort the coins in descending order.
2) Now, for each coin, we have a choice to make i.e. to choose it or not.
3) We define a function (in algorithmic sense, not a prog language function)
W(T,C) = min( W(T-Ci,C-Ci)+1 , W(T,C-Ci) ) ----for i=1 to #of coins
Before applying this condition, we will also be checking whether the current coin under consideration is greater than the required total sum T. If yes, we will ignore that coin. Maybe we can incorporate it within the definition of W(T,C)

I think we can use recursive to solve this problem.

private static ArrayList<Integer> allSizes = new ArrayList<Integer>();

public void getAllSize(int[] array, int sum, ArrayList<Integer> list, int index) {
if (getSum(list) == sum) {
allSizes.add(list.size());
return;
}

if (getSum(list) > sum) {
return;
}

for (int i = index; i < array.length; i++) {
list.add(array[i]);
getAllSize(array, sum, list, i+1);
list.remove(list.size()-1);
}
}

public int getMinNumberCoin(int[] array, int sum) {
getAllSize(array,sum,new ArrayList<Integer>(),0);
int min = Integer.MAX_VALUE;
for (int i = 0; i < allSizes.size(); i++) {
if (min > allSizes.get(i)) {
min = allSizes.get(i);
}
}

return min;
}

public int getSum(ArrayList<Integer> list) {
int result = 0;
for (int i = 0; i < list.size(); i++) {
result += list.get(i);
}

return result;
}
/**
* @param args
*/
public static void main(String[] args) {
Amazon16_MinNumberCoins a = new Amazon16_MinNumberCoins();
int[] array = {25,5,50,25,25,25,1};
System.out.print(a.getMinNumberCoin(array, 100));
}

Isn't it similar to ATM?

DP, O(N*S)

public int getMinCoins(int[] coins, int count)
{
int[] nums = new int[count+1];
for(int i=0; i<=count; i++)
nums[i] = -1;
nums[0] = 0;
for(int i=0; i<coins.length; i++)
{
int value = coins[i];

for(int j=count-value; j>0; j--)
{
if(nums[j]!=-1)
{
int n = nums[j]+1;
if(nums[j+value]==-1||n<nums[j+value])
{
nums[j+value] = n;
}
}
}
nums[value]=1;
}

return nums[count];
}

int min_no_coin(int a[],int N,int S)
{
int min[S+1];
for(int i=0;i<=S;i++)
min[i]=int_max;
min[0]=0;
for(int i=0;i<=S;i++)
{
for(int j=0;j<N;j++)
{
if(a[j]<=i && (min[i-a[j]]+1<min[i]))
min[i]=min[i-a[j]]+1;
}
printf("\n %d %d",i,min[i]);
}
if(min[S]!=int_max)
return min[S];
else return -1;
}

Sort the array containing values of coins. Take the sum and subtract it from descending order. For the remaining sum after subtraction , perform binary search to rest of the array , if number is found that we have found the Sum with min coins required. If not , continue subtracting and finding the coins

Coins should be sorted ascending for the code below to work, i sort at the begining of the method.

// coins need to be sorted ascending
int FindMinCoins(int []coins, int sum)
{
	int count = 0;
        coins.Sort(); // sort here
	for(int i=coins.Length-1; i>=0; i--)
	{
		if(coins[i] <= sum)
		{
			count += sum / coins[i];
			sum = sum % coins[i];
		}
		
		if(sum == 0)
		{
			break;
		}
	}

	if(sum != 0) // there is no solution
		return 0;

	return count;
}

classic DP