CODEWITHSUNDEEP
javaalgorithm
L-Samuels
L-Samuels

Reputation: 2832

Java Algorithm to solve vendor machine 'change giving' problem

As a graduate I went for an interview for a java development role and was doing pretty well in the technical examinations until i came up against this question.

If i was setting up a vending machine which (for simplicity) returned £2 change. How would i produce an implemtation that would list all the possible combinations of £2.

For e.g £1 + £1 , £1 + 50p + 50p, 50p + 50p + 50p + 50p and so on..

How could i list all the different combinations of £2.00 change possible by the vending machine.

I began to write something and this is what ive came up with so far.

Its almost working except can someone help me find out why its not expanding fully. A second pair of eyes will be grateful. And also any ways it can be optimised.

Thanks guys.

 private static void printCoins(int[] tempArray) {

    for (int i = 0; i < tempArray.length - 1; i++){

// to stop my array from printing out any non-denominator coins e.g  
    if (tempArray[i] > 0){
 System.out.print(tempArray[i] + ": ");
    }
    System.out.println("\n");
  }
}


public static void vendingMachine() {
    int[] denominations = {200,100, 50, 20, 10, 5, 2, 1};
    int[] tempArray = new int[50]; //combination of coins made
    int total = 200;
    int coinCombiIndex = 0, denomCoinIndex = 0;

    // whilst all denominations havent been visited
 while (denomCoinIndex < denominations.length)

     // if i have the correct change
    if (total - denominations[denomCoinIndex] == 0){
        tempArray[coinCombiIndex] = denominations[denomCoinIndex];

        denomCoinIndex++;  //increment so that next iteration starts with lower denom
        printCoins(tempArray); // return coins
    }

 // checks to see whether new total minus coin (denominator) is still >= 0
      else if (total - denominations[denomCoinIndex] >= 0) {

            // if so SUBTRACT from total and ADD coin to coin-combination-array
            total = total - denominations[denomCoinIndex];
            tempArray[coinCombiIndex] = denominations[denomCoinIndex];
            coinCombiIndex++;

            }
        else {
        denomCoinIndex++;

    }

    //  printCoins(tempArray);

}

my output

200: 

100: 100: 

100: 50: 50: 

100: 50: 20: 20: 10: 

100: 50: 20: 20: 5: 5: 

100: 50: 20: 20: 5: 2: 2: 1:

Upvotes: 0

Views: 11016

Answers (6)

user3499861
user3499861

Reputation: 1

public class VendeningMachine
{
    public static final int[] coins = {1, 5, 10, 25};
    public static final int[] coinMax = {200, 40, 20, 8};
    public static final int[] coinsString = { "Penny", "Nickle", "Dime", "Quarter"};

    public static void main(String[] args)
    {

    }


    public static void vendingMachine()
    {
        for ( int a = 0; a <= coinMax[0]; a++ ) {
            for ( int b = 0; b <= coinMax[1]; b++ ) {
                for ( int c = 0; c < coinMax[2]; c++ ) {
                    for ( int d = 0; d < coinMax[3]; d++ ) {
                        checkCoins(a, b, c, d);
                    }
                }
            }
        }
    }

    public static void checkCoins(int penny, int nickle, int dime, int quarter)
    {
        int total = coins[0] * penny + coins[1] * nickle + coins[2] * dime + coins[3] * quarter;

        if ( total == 200 )
            printCoins(penny, nickle, dime, quarter);

    }

    public static void printCoins(int penny, int nickle, int dime, int quarter)
    {
        System.out.println("Penney : " + penny + " Nickle: " + nickle + " Dime: " + dime + " Quarter: " + quarter);
    }

}enter code here

Upvotes: 0

Ricky Bobby
Ricky Bobby

Reputation: 7608

To answer your second question:

Try with only {20,10} you will see that your program is really not right .

You tried to transform my recurence into a loop, and I guess it's the best solution. But it's very difficult to do that in one loop (you're missing a lot of possibilities).

You can try to reinialise the while loop with different constraint at each step for example adding a new while loop around your loop like this one 

while (i<denominations.length){
             total=200;
             denomCoinIndex=i;
             tempArray = new int[1000]; 
             i++;

but it's still not enough ... so you will need to add some loop again until you treat all the cases.

I don't think your approach with a while loop is the good one here.

The easiest way would be to use for loop like this to treat all the possible solutions (from the similar question to your question):

 int total = 200;

               System.out. printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);

                int combos = 0;

                for (int q = 0; q <= total / 25; q++)
                {
                    int total_less_q = total - q * 25;
                    for (int d = 0; d <= total_less_q / 10; d++)
                    {
                        int total_less_q_d = total_less_q - d * 10;
                        for (int n = 0; n <= total_less_q_d / 5; n++)
                        {
                            int p = total_less_q_d - n * 5;
                            System.out.printf("%d\t%d\t%d\t%d\n", q, d, n, p);
                            combos++;
                        }
                    }
                }

                System.out.printf("%d combinations\n", combos);

Hope it helps

Upvotes: 1

Rag
Rag

Reputation: 6593

Algorithm F on (in-text) page 7 is exactly what you're looking for. :)

http://www-cs-staff.stanford.edu/~uno/fasc3a.ps.gz

Upvotes: 0

Ricky Bobby
Ricky Bobby

Reputation: 7608

Let say your possible coins are x1 ...xn :

if you're asked to print all the possiblities for $2 then you could print recursively all the possibilities for :

2-x1
2-x2
..
2-xn

Yoou will eventually get all the solutions

You can initialise this recursive process with amount-xi = 0 then print

Upvotes: 1

Jim Garrison
Jim Garrison

Reputation: 86774

Reframe the problem as follows: Given a standard (modern) car odometer that registers 6 digits with no fractions, find all possible values where the sum of the digits is some value, say 15. If you can solve that, you can solve the given problem.

Upvotes: 0

panzerschreck
panzerschreck

Reputation: 3642

Probably get started on looking at Dynamic programming. However you could any approach problem for that matter trivially. How would you do that manually ??. Jot down the steps. Convert it into an algorithm yourself. Probably studying Permutations & Combinations would help for better understanding of the problem you have stated.

Hope it helps.

Upvotes: 1

Related Questions