Dynamic American Change.cpp

// Programmer: Evan Heidebrink
// Description: demonstation of dynamic programming applied to calculating the minimal set of American coins/bills that sums to a value.

#include <iostream>
#include <vector>
#include <set>
#include <chrono>
using namespace std::chrono;
using std::cout;
using std::cin;
using std::vector;
using std::multiset;

enum { PENNY = 1, NICKEL = 5, DIME = 10, QUARTER = 25, 
       ONE_DOLLAR = 100, FIVE_DOLLAR = 500, TEN_DOLLAR = 1000, TWENTY_DOLLAR = 2000, FIFTY_DOLLAR = 5000, HUNDRED_DOLLAR = 10000 };

const unsigned DENOMINATIONS[10] = { PENNY, NICKEL, DIME, QUARTER, 
                                     ONE_DOLLAR, FIVE_DOLLAR, TEN_DOLLAR, TWENTY_DOLLAR, FIFTY_DOLLAR, HUNDRED_DOLLAR };

multiset<unsigned> americanDenominations(const unsigned balance);
void outputDenominations(const multiset<unsigned>& denominations);

int main()
{
    unsigned balance = 0;
    multiset<unsigned> minimalDenominations;

    while (balance != -1)
    {
        cout << "Balance in cents (or -1 to quit): ";
        cin >> balance;

        // verify input
        while (balance <= 0 && balance != -1)
        {
            cout << "Balance in cents (or -1 to quit): ";
            cin >> balance;
        }

        if (balance != -1)
        {
            // get the minimalDenominations and time it in nanoseconds
            auto startTime = high_resolution_clock::now();
            minimalDenominations = americanDenominations(balance);
            auto endTime = high_resolution_clock::now();
            auto duration = duration_cast<nanoseconds>(endTime - startTime).count();

            // output results
            outputDenominations(minimalDenominations);
            cout << "Execution time: " << duration << " nanoseconds\n\n";
        }
    }

    system("pause");
}

/**
 * Dynamically calculate the minimum denominations necessary that sums to balance.
 * O(n) time complexity.
 * 
 * @param balance The balance for which the minimal denominations needs to be calculated.
 * 
 * @return A multiset of denominations of minimal length that sums to balance.
 */
multiset<unsigned> americanDenominations(const unsigned balance)
{
    // cache. denominationsSets[i] = a set of denominations that sums to i of minimal length
    vector<multiset<unsigned>> denominationsSets;

    denominationsSets.resize(balance + 1);

    // calculate minimal sets from 1 to balance
    for (unsigned change = 1; change <= balance; change++)
        for (const auto& denomination : DENOMINATIONS)
            if (change >= denomination)
            {
                // create a potentially smaller set using a denomination
                multiset<unsigned> addDenomination = denominationsSets[change - denomination];
                addDenomination.insert(denomination);

                // if the new set is optimal, use it
                if ((denominationsSets[change].size() > addDenomination.size()) || (denominationsSets[change].empty()))
                    denominationsSets[change] = addDenomination;
            }

    return denominationsSets[balance];
}

/**
 * Helper function to output the number of each denomination instances.
 *
 * @param denominations The set containing denominations.
 */
void outputDenominations(const multiset<unsigned>& denominations)
{
    unsigned pennies = 0;
    unsigned nickels = 0;
    unsigned dimes = 0;
    unsigned quarters = 0;
    unsigned oneDollars = 0;
    unsigned fiveDollars = 0;
    unsigned tenDollars = 0;
    unsigned twentyDollars = 0;
    unsigned fiftyDollars = 0;
    unsigned hundredDollars = 0;

    // calculate instances for each denomination
    for (const auto& denomination : denominations)
        switch (denomination)
        {
            case PENNY: pennies++; break;
            case NICKEL: nickels++; break;
            case DIME: dimes++; break;
            case QUARTER: quarters++; break;
            case ONE_DOLLAR: oneDollars++; break;
            case FIVE_DOLLAR: fiveDollars++; break;
            case TEN_DOLLAR: tenDollars++; break;
            case TWENTY_DOLLAR: twentyDollars++; break;
            case FIFTY_DOLLAR: fiftyDollars++; break;
            case HUNDRED_DOLLAR: hundredDollars++; break;
        }

    if (pennies != 0)
        if (pennies > 1)
            cout << pennies << " pennies\n";
        else
            cout << pennies << " penny\n";

    if (nickels != 0)
        if (nickels > 1)
            cout << nickels << " nickels\n";
        else
            cout << nickels << " nickel\n";

    if (dimes != 0)
        if (dimes > 1)
            cout << dimes << " dimes\n";
        else
            cout << dimes << " dime\n";

    if (quarters != 0)
        if (quarters > 1)
            cout << quarters << " quarters\n";
        else
            cout << quarters << " quarter\n";

    if (oneDollars != 0)
        if (oneDollars > 1)
            cout << oneDollars << " one-dollar bills\n";
        else

    if (fiveDollars != 0)
        if (fiveDollars > 1)
            cout << fiveDollars << " five-dollar bills\n";
        else
            cout << fiveDollars << " five-dollar bill\n";

    if (tenDollars != 0)
        if (tenDollars > 1)
            cout << tenDollars << " ten-dollar bills\n";
        else
            cout << tenDollars << " ten-dollar bill\n";

    if (twentyDollars != 0)
        if (twentyDollars > 1)
            cout << twentyDollars << " twenty-dollar bills\n";
        else
            cout << twentyDollars << " twenty-dollar bill\n";

    if (fiftyDollars != 0)
        if (fiftyDollars > 1)
            cout << fiftyDollars << " fifty-dollar bills\n";
        else
            cout << fiftyDollars << " fifty-dollar bill\n";

    if (hundredDollars != 0)
        if (hundredDollars > 1)
            cout << hundredDollars << " hundred-dollar bills\n";
        else
            cout << hundredDollars << " hundred-dollar bill\n";
}