CareerCup

Hey I think it is a typical case of unbounded knapsack with limits on the number of coins in each denomination to be chosen

Assuming denomination to be 25 cents(quarters), 10 cents(dimes), 5 cents(nickels) and 1 cent(pennies). Printing number of ways possible to make change for "n" cents:

Algorithm : We know that makeChange(100):
= makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100 using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)

Can we reduce this further? Yes!
= makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1

Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dimes.

Code:

#include<stdio.h>

int makeChange(int n, int denom) {
        int next_denom = 0;
        switch (denom) {
        case 25:
               next_denom = 10;
               break;
        case 10:
               next_denom = 5;
               break;
        case 5:
               next_denom = 1;
               break;
        case 1:
               return 1;
        }
        int i,ways = 0;
        for (i = 0; i * denom <= n; i++) {
               ways += makeChange(n - i * denom, next_denom);
        }
        return ways;
       }
int main(){
	   int n = 100;
       printf("%d",makeChange(n, 25));
       return 1;
}

> DP , are you sure?

Yes. The outer loop is over coins, not denominations.

DP would always work but for some denominations (like the US), even greedy would work!

Can anybody give the algo ?

DP - Dynamic Programming

Start with highest denomination, check how much you can much change you can make with it, if you can't goto next smallest one, if you use it as much as possible and for remaining amount, goto next smaller denomination. This is the greedy solution.

DP is a overkill in this scenario. Memoization is better approach. As DP solve all the possible sub-problems whether needed or not. Memoization is same old recursive approach which note down what is already solved.

So, we have:

v = {1, 5, 10, 25, 50, 100} // domincations US exmaple
c = {2, 4, 2, 4, 1, 2} // count of each coin in the pocket.

It can be represented as:
a = {1,1, 5,5,5,5, 10, 10, } // all coin domination their count times.

F(n, AMOUNT) = true if a[n] == AMOUNT // exact domination
F(n, AMOUNT) = false if n == 0 or AMOUNT < 0 // no coins available
F(n, AMOUNT) = F(n-1, AMOUNT) OR F(n-1, AMOUNT-a[n])

So, you need to have an array of size results[n][AMOUNT], each element can contains 3 values:

UNKNOWN
TRUE
FALSE

bool F(int n, int amount)
{
   if (n == 0 || amount < 0)
   {
       return false;
   }

   if (amount == a[n])
   {
       return true;
   }

   if (result[n][amount] == UNKNOWN) 
   {
       result[n][amount] = F(n-1, AMOUNT) || F(n-1, AMOUNT-a[n]);
   }
   
   return result[n][amount];

}

i have another theory. Can we think this as a number coin counts are digits and coin values are digit weights. eg we have coins 50 20 5 1 and counts 2 5 2 5 and we want to reach 33 we can do a binary search like search between 2525 and 0000

<pre lang="" line="1" title="CodeMonkey97168" class="run-this">import java.util.ArrayList;
import java.util.List;

/**
*
* @author Pragalathan
*/
class CoinDenomination {

static class Coin {

int value;
int count;

public Coin(int value, int count) {
this.value = value;
this.count = count;
}

@Override
public String toString() {
return "(" + value + "x" + count + ")";
}
}
Coin[] coins;

public CoinDenomination(Coin[] coins) {
this.coins = coins;
}

List<Coin> getChange(int amount) {
List<Coin> change = new ArrayList<Coin>();
getChange(amount, 0, change);
return change;
}

private boolean getChange(int balance, int coinIndex, List<Coin> change) {
if (coinIndex >= coins.length) {
return false;
}
Coin coin = coins[coinIndex];
int count = Math.min(coin.count, balance / coin.value);

for (int i = count; i >= 0; i--) {
int newBalance = balance - i * coin.value;
if (newBalance == 0) {
change.add(new Coin(coin.value, i));
return true;
}
if (getChange(newBalance, coinIndex + 1, change)) {
if (i > 0) {
change.add(new Coin(coin.value, i));
}
return true;
}
}
return false;
}

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int[] values = {1, 5, 10, 25, 50, 100};
int[] counts = {3, 4, 2, 4, 1, 2};

Coin[] coins = new Coin[values.length];
for (int i = 0; i < values.length; i++) {
coins[i] = new Coin(values[i], counts[i]);
}
CoinDenomination cd = new CoinDenomination(coins);
int amount = 33;
System.out.println(amount + ": " + cd.getChange(amount));

values = new int[]{1, 10, 25, 50, 100};
counts = new int[]{3, 3, 4, 1, 2};

coins = new Coin[values.length];
for (int i = 0; i < values.length; i++) {
coins[i] = new Coin(values[i], counts[i]);
}
cd = new CoinDenomination(coins);
amount = 205;
System.out.println(amount + ": " + cd.getChange(amount));
}
}
</pre><pre title="CodeMonkey97168" input="yes">
</pre>

<pre lang="" line="1" title="CodeMonkey97457" class="run-this">import java.util.HashMap;
import java.util.LinkedList;


/**
* @author j
* You have coins with different denominations and you have limited number of each denominations (some maybe zero),
* how will you determine if you can supply the given change. DP , are you sure? think again.
*/
class G87CoinComposition {


/**
* @param n
* @param k
* @param coin
* @param coinUsed - output,
* @returns the # of minimal coins used, in coinUsed you get the combination of the coins to build n....
* this routine is using Dynamic Programming to build the optimal solution
* c[i] minimum number of coins we need to build for i;
* c[i] = infinity i < 0
* c[i] = 0; j = 0
* c[i] = 1+ minimum {c[i] - d[j]} 0 <= j < den.length...
*/
public static int computeMinNumberCoinsForChangeSolution(int n, int k, int[] coin, LinkedList<Integer> coinUsed) {
int[] c = new int[n+1];
int[] d = new int[n+1];
c[0] = 0;
d[0] = 0;
for (int i = 1; i <= n; i++) {
c[i] = Integer.MAX_VALUE;
for (int j = 0; j < k; j++) {
if (coin[j] <= i && 1 + c[i - coin[j]] < c[i]) {
c[i] = 1 + c[i - coin[j]];
d[i] = coin[j];
}
}
}
buildCoinUsedForChange(d, n, coinUsed);
return c[n];
}



private static void buildCoinUsedForChange(int[] d, int i, LinkedList<Integer> coinUsed){
if(i > 0){
buildCoinUsedForChange(d, i-d[i], coinUsed);
coinUsed.add(d[i]);
}
}

/**
* @param coinUsed
* @param limit contains the constrains for coin selections, key = coin, value = max number possible
* @return true for success , false otherwise
*/
public static boolean checkForMinChange(int n, int k, int[] coin, LinkedList<Integer> coinUsed, HashMap<Integer, Integer> limit){
computeMinNumberCoinsForChangeSolution(n, k, coin, coinUsed);
for(Integer cu: coinUsed){
if(!limit.containsKey(cu)) return false;
int v = limit.get(cu)-1;
if( v <=0){
limit.remove(cu);
} else {
limit.put(cu, v);
}
}
return true;
}

public static void main(String[] args) {
int[] coin = { 1, 5, 10, 20, 25, 50 };
LinkedList<Integer> coinUsed = new LinkedList<Integer>();
HashMap<Integer, Integer> limit = new HashMap<Integer, Integer>();
for (int i = 0; i < coin.length; i++) {
limit.put(coin[i], 10);
}
System.out.println(checkForMinChange(183, coin.length, coin, coinUsed, limit));
for(Integer cu: coinUsed){
System.out.printf("%d ", cu);
}


// Simulate negative case, limit the usage for 1 cent to only one coin
coinUsed = new LinkedList<Integer>();
for (int i = 0; i < coin.length; i++) {
limit.put(coin[i], 10);
}
limit.put(1, 1);

System.out.println("\n"+checkForMinChange(183, coin.length, coin, coinUsed, limit));
for(Integer cu: coinUsed){
System.out.printf("%d ", cu);
}
}
}

</pre><pre title="CodeMonkey97457" input="yes">
</pre>

public static void main(String[] args) {
		int [] D = {50, 25, 10, 1};
		int [] limit = {2, 1, 2, 5};		
		makeChangeLimitedCoins(D, limit, 30);
	}
	
	public static void makeChangeLimitedCoins(int [] D, int [] S, int N) {
		int [] C = new int [N+1];
		C[0] = 0;
		
		int len = D.length;
		int [][] track = new int[N+1][len];
		for (int i=0; i<len; i++) {
			track[0][i] = S[i];
		}
		
		for (int j=1; j<=N; j++) {
			C[j] = Integer.MAX_VALUE;
			for (int k=0; k<len ; k++) {
				if (j >= D[k] && (C[j-D[k]] < Integer.MAX_VALUE) && (track[j-D[k]][k] > 0)) {
					if ((C[j] > 1+C[j-D[k]])) {
						C[j] =  1 + C[j-D[k]];						
						track[j][k] = track[j-D[k]][k] - 1;
					} else {
						track[j][k] = track[j-D[k]][k];
					}
				} else if (j < D[k] ){
					track[j][k] = track[0][k];
				}
			}
		}
		System.out.println("Printing Coin Value and Change:");
		for (int i=1; i<=N; i++) {
			if (C[i] == Integer.MAX_VALUE) {
				System.out.println(i + ":" + " Not Possible");
			} else {
				System.out.println(i + ":" + C[i]);
			}
		}
		System.out.println();
		
		for (int i=0; i<=N ;i++) {
			System.out.print(i + ": ");
			for (int j=0; j<len; j++) {				
				System.out.print(track[i][j] + " ");
			}
			System.out.println();
		}
	}

public static boolean possibleSum(int [] array, int sum) {
		if (sum == 0) return true;
		if (sum < 0) return false;
		
		if (array.length == 0) return false;
		
		// if a is part of solution
		int [] sub = Arrays.copyOfRange(array, 1, array.length);
		if (possibleSum(sub, sum - array[0])) {
			return true;
		// not include this one
		} else {
			return possibleSum(sub, sum);
		}
	}

I did not get the question, properly.
But if we are to get the change in minimum number of coins for an amount, then we can store the values from 0 to (LCM of all denominations) by checking all combinations.
Above that we will just
find for amount % LCM, which we already have,
+ (amount/LCM)*(LCM/maxDenom).

we can use a graph here with all of the coins as vertices and searching for a path with a specific length. if we go over the len of the path we cut it. This solution will be slow but just wanted to mention the idea.

I think both greedy and dynamic are work.
greedy:

int getMaxDenomination(map<int, int> m, int change) {
int max = -1;
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
if (it->second > 0 && it->first > max && it->first <= change) {
max = it->first;
}
}
return max;
}

bool supply(map<int, int> m, int change) {
assert(change > 0);
int max = getMaxDenomination(m, change);
if (max != -1) {
if (change - max > 0) {
m[max] = m[max] - 1;
return supply(m, change - max);
} else {
return true;
}
} else {
return false;
}
}

void main() {
map<int, int> m;
m[1] = 2; // has 2 pennies
m[5] = 3;
m[25] = 4;
m[50] = 12;
m[100] = 1;
cout << supply(m, 20) << endl;
}

Here is the one in C#.

public bool MakeChanges(int[] coinType, int[] coinNumber, int change)
        {
            return this.MakeChanges(coinType, coinNumber, change, 0);
        }


        protected bool MakeChanges(int[] coinType, int[] coinNumber, int change, int index)
        {
            if (change < 0)
            {
                throw new ArgumentException();
            }
            if (change == 0)
            {
                return true;
            }
            else
            {
                int totalCoin = 0;
                for (int i = 0; i < coinType.Length; i++)
                {
                    totalCoin += coinType[i] * coinNumber[i];
                }

                if (change > totalCoin)
                {
                    return false;
                }
                if (change == totalCoin)
                {
                    return true;
                }
                else
                {
                    //Less than total

                    for (int i = index; i < coinType.Length; i++)
                    {
                        int temp = coinNumber[i];
                        for (; coinNumber[i] >= 0; )
                        {
                            coinNumber[i]--;
                            bool result = MakeChanges(coinType, coinNumber, change, i);
                            if (result)
                            {
                                return result;
                            }
                        }
                        coinNumber[i] = temp;
                    }
                }
            }

            return false;
        }

Test Code:

/// <summary>
        ///A test for MakeChanges
        ///</summary>
        [TestMethod()]
        public void MakeChangesTest()
        {
            Google1 target = new Google1(); 
            int[] coinType = {25, 10, 5, 1}; 
            int[] coinNumber = {3, 9, 9, 9}; 
            int change = 142; 
            bool expected = true; // TODO: Initialize to an appropriate value
            bool actual;
            actual = target.MakeChanges(coinType, coinNumber, change);
            Assert.AreEqual(expected, actual);

            for (int i = 0; i < coinNumber.Length; i++)
            {
                Console.WriteLine(coinNumber[i]);
            }
        }

Here we have to follow a top down approach (greedy one) with back tracking.

#include <iostream>
using namespace std;
bool coinChange(int set[],int count[],int m,int sum){
if(m<=0&&sum>0||sum<0)
return false;
if(sum==0)
return true;
if(set[m-1]<=sum&&count[m-1]>0){
bool ans1=coinChange(set,count,m-1,sum);
if(ans1)return ans1;
--count[m-1];
bool ans2=coinChange(set,count,m,sum-set[m-1]);
if(!ans2)++count[m-1];
return ans2;
}
return coinChange(set,count,m-1,sum);
}
int main() {
int set[]={3,7,11,16};
int count[]={1,2,3,4};
cout<<coinChange(set,count,4,26);
return 0;
}

#include <iostream>
using namespace std;

int numOfWays(int n, int coin) {
	if(coin == 1) return 1;
	int i, ways = 0, maxNum = n /coin, nextCoin = ( coin == 25 ? 10 : (coin == 10 ? 5 : (coin == 5 ? 1 : 1)));
		
	for(i = 0; i <= maxNum; i++)
		ways += numOfWays(n - i * coin, nextCoin);
        return ways;
}

int main() {
	int n;
	cin >> n;
	cout << numOfWays(n, 25);

        return 0;
}

Greedy approach will work here as the question is not about "how optimally the change is provided" but "if we can provide change or not". Am I missing something?

What is DP?

yeah, I think Greedy approach work for this problem but not the optimal solution.