4
\$\begingroup\$

I have just started out learning C++ and I am trying to write out a simple bills' dispenser machine as an exercise.

Upon user input, the system is to check if it can pay out the amount but only in 20 and 50 bills, and it should return with the minimum number of bills.

I need someone to point out and tell me if the following code I have wrote if it is viable (it seems to be working when I tested it myself, but that is too one sided). What about the structure?

There are 2 parts that I did - the first code simply by extending the main function while the latter is done by introducing the functions.

#include <iostream>
using namespace std;

int main()
{
    int inputAmt;

    cout << "This machine only dispense in $20 and $50 bills only" << endl;
    cout << "Enter in the amount to be withdraw : " << endl;
    cin >> inputAmt;

    // Decides the number of $50 bills to be dispense
    int fiftyBill;
    fiftyBill = inputAmt/50;

    int remainderAmt;
    remainderAmt = inputAmt - (fiftyBill*50);

    // Test the Remainder Amount if it is even
    int remE;
    remE = remainderAmt % 20;

    if (remE >= 10 || remE <= 20 )
    {
        // If it is not, reduced $50 by 1 and add it to the remainder amount
        fiftyBill = fiftyBill - 1;
        remainderAmt = remainderAmt + 50;
    }

    // Decides the number of $20 bills to be dispense
    int twentyBill;
    twentyBill = remainderAmt / 20;

    // Output Message
    cout << "Number of $50 bills : " << fiftyBill << endl;
    cout << "Number of $20 bills : " << twentyBill << endl << endl;

    cout << "Number of bills dispensed is " << fiftyBill + twentyBill << endl;

    int leftoverAmt;
    leftoverAmt = inputAmt - (fiftyBill * 50) - (twentyBill * 20);
    if (leftoverAmt != 0)
    {
        cout << "There are a leftover of $" << leftoverAmt << " that cannot be dispensed." << endl;
    }
}

Lastly, I tried to integrate 2 functions bool dispense (int amt) (returns true if the amount indicated can be dispensed in combinations of 20 and 50 bills, false otherwise) and int dispenseFif (int amt) (returns the number of 50 bills to dispense that will results in least number of notes being dispensed).

#include <iostream>
using namespace std;

bool canDispense (unsigned int amount);
int dispense50s (unsigned int amount);

int main()
{
    int inputAmt;
    cout << "This machine only dispense in $20 and $50 bills only" << endl;
    cout << "Enter in the amount to be withdraw : " << endl;
    cin >> inputAmt;

    canDispense(inputAmt);
}

bool canDispense (unsigned int amount)
{    
    int fifAmt = dispense50s(amount);
    int remainderAmt;
    remainderAmt = amount - (fifAmt*50);

    // Test the Remainder Amount if it is even
    int remE;
    remE = remainderAmt % 20;
    cout << "remE : " << remE << endl << endl;

    if (remE >= 10 || remE >= 20 )
    {
        fifAmt = fifAmt - 1;
        remainderAmt = remainderAmt + 50;
    }

    // Decides the number of $20 bills to be dispense
    int twentyBill;
    twentyBill = remainderAmt / 20;

    int leftoverAmt;
    leftoverAmt = amount - (fifAmt * 50) - (twentyBill * 20);

    if (leftoverAmt == 0)
        {
            // Output Message
            cout << "(2) Number of $50 bills : " << fifAmt << endl;
            cout << "(2) Number of $20 bills : " << twentyBill << endl;

            cout << "(2) Number of bills dispensed is " << fifAmt + twentyBill << endl; 
            return true;
        }
    else
        {
        cout << "The amount is impossible! Please try again... " << endl;
        return false;
        }

}

int dispense50s (unsigned int amount)
{
    // Decides the number of $50 bills to be dispense
    int fiftyBill;
    fiftyBill = amount/50;
    return fiftyBill;
}
\$\endgroup\$
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Dan Pantry Feb 22 '16 at 8:57
  • \$\begingroup\$ @DanPantry Sorry about that. I will take note of it next time! \$\endgroup\$ – dissidia Feb 22 '16 at 10:11
1
\$\begingroup\$

This is a tricky problem to solve. In the general case, the requires to solve. It is possible to write a simpler algorithm that works for $20 and $50 only, but yours is buggy:

This machine only dispense in $20 and $50 bills only
Enter in the amount to be withdraw : 
30
remE : 10

(2) Number of $50 bills : -1
(2) Number of $20 bills : 4
(2) Number of bills dispensed is 3

Furthermore, if (remE >= 10 || remE >= 20 ) in the second solution looks wrong.


If I had to write a quick-and-dirty non-generalized solution for $50 and $20, I would write it this way:

#include <cassert>
#include <iostream>
#include <iomanip>

/**
 * Composes the given amount as a number of 50-dollar bills and 20-dollar
 * bills (as out-parameters).  Returns the total number of bills needed, or -1
 * if the amount cannot be formed.
 */
int split_50_20_bills(int amount, int *num_50, int *num_20) {
    if (amount < 0 || amount == 10 || amount == 30 || amount % 10) {
        return -1;
    } else {
        *num_50 = (amount % 20) ? ((amount - 50) / 100) * 2 + 1 :
                                  (amount / 100) * 2;
        *num_20 = (amount - 50 * *num_50) / 20;
        assert(amount == 50 * *num_50 + 20 * *num_20);
        return *num_50 + *num_20;
    }
}

int main()
{
    for (int amt = 0; amt <= 1000; amt += 10) {
        int num_50, num_20;
        int total = split_50_20_bills(amt, &num_50, &num_20);
        std::cout << std::setw(4) << amt;
        if (total < 0) {
            std::cout << " cannot be formed\n";
        } else {
            std::cout << " = " << std::setw(2) << num_50 << " x $50 + "
                               << std::setw(2) << num_20 << " x $20 ("
                               << std::setw(2) << total << " bills)\n";
        }
    }
}

Note that one function passes back four pieces of information:

  • Whether it's possible to form the amount
  • If so, how many bills it will take altogether
  • How many $50 bills
  • How many $20 bills
\$\endgroup\$
  • \$\begingroup\$ Okay, I have been working with hundreds/thousands and did not bother to try with tens (my bad on this..) Can you give me any hints on the solution if (remE >= 10 || remE >= 20 ) cause I feel that I am pretty much brute-forcing through and this is the only way so far that I can think of.. \$\endgroup\$ – dissidia Feb 22 '16 at 8:22
  • \$\begingroup\$ wow.. that is very descriptive but unfortunately there are quite some modules that you have used in which I do not really understand :x as I have only learned the basics of the basics.. but can I ask how do you derive amount == 10 || amount == 30 || amount % 10 \$\endgroup\$ – dissidia Feb 22 '16 at 10:25
0
\$\begingroup\$

My previous solution (see below) described a greedy algorithm which is not really an answer to this question.

My new answer is now an improved dispense method that should solve the problem correctly:

#include <iostream>
#include <array>
#include <map>

using namespace std;

template <class T, size_t N>
std::map<T, T> dispense(T in_amount, const std::array<T, N>& in_billValues, T& out_rest)
{
    if (in_amount <= 0) return std::map<T, T>();
    if (in_billValues.size() < 0) return std::map<T, T>();


    std::array<T, N> billValues = in_billValues;
    std::sort(billValues.begin(), billValues.end());

    std::map<T, T> bills;
    for (size_t i = 0; i < billValues.size(); i++)
    {
        if(billValues[i] == 0) return std::map<T, T>(); //There are no 0 dollar bills
        bills[billValues[i]] = in_amount / billValues[i];
        in_amount -= billValues[i] * bills[billValues[i]];
    }

    //Try push rest somewhere it fits
    for (size_t i = 0; i < billValues.size() - 1; i++) //From low to high
    {
        for (size_t j = billValues.size() - 1 ; j > i ; j--) //From high to low
        {
            for (int k = bills[billValues[i]]; k > 0; k--) //Take k bills of the low value
            {
                if (((billValues[i] * k) + in_amount) % billValues[j] == 0) //Try to convert into high value
                {
                    int tmp = bills[billValues[i]] - k;
                    bills[billValues[i]] -= k;
                    bills[billValues[j]] += ((billValues[i] * k) + in_amount) / billValues[j];
                    k = tmp;
                    in_amount = 0;
                }
            }
        }
    }

    //Try to minimize bills
    for (size_t i = 0; i < billValues.size() - 1; i++) //From low to high
    {
        for (size_t j = billValues.size() - 1; j > i; j--) //From high to low
        {
            for (int k = bills[billValues[i]]; k > 0; k--) //Take k bills of the low value
            {
                if ((billValues[i] * k) % billValues[j] == 0) //Try to convert into high value
                {
                    int tmp = bills[billValues[i]] - k;
                    bills[billValues[i]] -= k;
                    bills[billValues[j]] += (billValues[i] * k) / billValues[j];
                    k = tmp;
                }
            }
        }
    }

    out_rest = in_amount;
    return bills;
}

int main()
{
    int inputAmt;

    cout << "This machine only dispense in $20 and $50 bills only" << endl;
    cout << "Enter in the amount to be withdraw : " << endl;
    cin >> inputAmt;

    int leftOver = 0;
    std::array<int, 2> billValues = {50, 20};
    std::map<int, int> bills = dispense(inputAmt, billValues, leftOver);

    // Output Message
    cout << "Number of $50 bills : " << bills[50] << endl;
    cout << "Number of $20 bills : " << bills[20] << endl << endl;
    cout << "Number of bills dispensed is " << (bills[50] + bills[20]) << endl;
    if (leftOver != 0)
    {
        cout << "There are a leftover of $" << leftOver << " that cannot be dispensed." << endl;
    }
}

Some tests:

This machine only dispense in $20 and $50 bills only
Enter in the amount to be withdraw :
80
Number of $50 bills : 0
Number of $20 bills : 4

Number of bills dispensed is 4

---------------------

This machine only dispense in $20 and $50 bills only
Enter in the amount to be withdraw :
130
Number of $50 bills : 1
Number of $20 bills : 4

Number of bills dispensed is 5

---------------------

This machine only dispense in $20 and $50 bills only
Enter in the amount to be withdraw :
105
Number of $50 bills : 2
Number of $20 bills : 0

Number of bills dispensed is 2
There are a leftover of $5 that cannot be dispensed.

---------------------

This machine only dispense in $20 and $50 bills only
Enter in the amount to be withdraw :
1024
Number of $50 bills : 20
Number of $20 bills : 1

Number of bills dispensed is 21
There are a leftover of $4 that cannot be dispensed.

This solution allows you to change the number and kind of notes as it is not hardcoded. For example, you can easily adjust it to accept bills with the values 500, 200, 100, 50, 20, 10, 5, 2, 1, and just need to change the call to the dispense method:

int main()
{
    int inputAmt;

    cout << "Enter in the amount to be withdraw : " << endl;
    cin >> inputAmt;

    int leftOver = 0;
    std::array<int, 9> billValues = {500, 200, 100, 50, 20, 10, 5, 2, 1};
    std::map<int, int> bills = dispense(inputAmt, billValues, leftOver);

    // Output Message
    int totalBills = 0;
    for (int billValue : billValues)
    {
        cout << "Number of $" << billValue << " bills : " << bills[billValue] << endl;
        totalBills += bills[billValue];
    }
    cout << "Number of bills dispensed is " << totalBills << endl;
    if (leftOver != 0)
    {
        cout << "There are a leftover of $" << leftOver << " that cannot be dispensed." << endl;
    }
}

The output could look like this:

This machine only dispense in $20 and $50 bills only
Enter in the amount to be withdraw :
123456
Number of $500 bills : 246
Number of $200 bills : 2
Number of $100 bills : 0
Number of $50 bills : 1
Number of $20 bills : 0
Number of $10 bills : 0
Number of $5 bills : 1
Number of $2 bills : 0
Number of $1 bills : 1
Number of bills dispensed is 251

Unfortunately, this solution is not the fastest.

\$\endgroup\$
  • \$\begingroup\$ The greedy algorithm won't work. 130 = 1 × 50 + 4 × 20. \$\endgroup\$ – 200_success Feb 22 '16 at 15:08
  • \$\begingroup\$ @200_success Thank you - I updated my question. \$\endgroup\$ – Simon Kraemer Feb 22 '16 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.