CareerCup

Seems like a linear programming problem to me. Let x1,x2...xn be the no of coins of each type required to make the given sum. So, we have to minimize x1+x2+...+xn with the constraints,
k1x1+k2x2+.....knxn=sum, k1..kn being the exchange values
x1, x2..xn are positive integers
x1<=m1, m1 is the no of available coins of 1st type..and so on
x2<=m2
....
xn<=mn

Assumption is that its possible to provide change. (For that we can assume that there is unit coin available)
We will have to define one objective for dispensing the coins.
"Machine would like to dispense as few coins as possible"

Then this problem can be either solved by Greedy approach or dynamic programming approach.

Greedy approach : At any given stage, use the highest valued coin possible. Lets suppose you have to make change for 98 units and you have two 50 unit coins, one 20 unit coin and four 10 unit coins and unlimited 1 unit coins.
1st Stage : Use one 50 unit. (we can not use 2 as that would exceed the given amount)
2nd Stage : We could have used two 20 unit ones but we have only one. Use one. Remaining amount is 28.
3rd Stage : Use two 10 unit ones.
4th Stage : Use 8 one unit coins.

Another approach is Dynamic Programming.

Assume that the coins are of the value v1, v2, vn. We have to make change for value j.

MinNoOfCoins(j) = min{for all v in [v1-vn] calculate MinNoOfCoins{ j - v} } + 1

if m1,m2......mn b d max no of coins available of each type of x1,x2....xn coins respectively.
bill amount =amt, amount given by d customer = tot.
so change to b given = x i.e. tot-amt
k1x1+k2x2....knxn=x where k1,k2...kn b d no of each coins required .
initially k1=k2=.....kn=0
if x1,x2....xn are sorted (assuming x1 is highest and xn is least)then
while(x>x1)
{
if(k1<=m1)
{
x=x-x1;
k1++;
}
}
while(x>x2)
{
if(k2<=m2)
{
x=x-x2;
k2++;
}
}
.
.
.
.
.
.while(x>xn)
{
if(kn<=mn)
{
x=x-xn;
kn++;
}
}

This is COIN CHANGE PROBLEM. (well know)

onestopinterviewprep.blogspot.com/2014/03/vending-machine-problem-dynamic.html

You could change denomination array as you want. Please test it. Thank you:)

public class VendingMachine {
	
	static int[] deno = {20,15,10,5,2,1};
	
	public static void change(int amount){
		int[] tab = new int[amount + 1];
		tab[0] = 0;
		for(int i=1;i<=amount;i++){
			int min = Integer.MAX_VALUE;
			for(int k=0;k<deno.length;k++){
				if(i - deno[k]>=0){
					int tmp = tab[i-deno[k]] + 1;
					if(tmp < min){
						min = tmp;
					}
				}
			}
			tab[i] = min; 
		}
		System.out.println(tab[amount]);
		return;
	}
	
	public static void main(String[] args) {
		change(30);
	}

}

public static void Change()
        {
            double[] change = new double[] {10.00, 5.00, 1.00, 0.50, 0.25, 0.01 };
            double ItemPrice = 8.25;
            double Quantity = 2.00;
            double CustomerAmnt = 20.00;
            double Amount = CustomerAmnt - (ItemPrice * Quantity);
            for (int i = 0; i < change.Length; i++)
            {
                if (Amount >= change[i])
                {
                    double remainder = (Amount % change[i]);
                    double times = (Amount / change[i])-(remainder/change[i]);
                    Console.WriteLine("{0} * {1} = {2}", change[i], times, change[i]*times);
                    Amount = Amount- (change[i] * times);
                }
            }
        }