Minimizing Number of Coins After Buying An Item

Question

I came up with this algorithmic problem while trying to solve a problem in my (adventure-based) program. There are 5 different types of coins called, A,B,C,D,E (from most valuable to least valuable). The conversions between the coin values are AtoE, BtoE, CtoE, DtoE (i.e. AtoE means that a coin of type A is worth AtoE times the value of a coin of type E). The struct Currency represents how much money a customer has. The goal of the function

template <int AtoE, int BtoE, int CtoE, int DtoE>
void purchase (int numCoins, CoinType coinType, int a, int b, int c, int d, int e)

is to have the customer (who has a coins of type A, b coins of type B, etc...) to purchase an item whose price is numCoins coinTypes while minimizing the amount of coins he has after receiving the change. Can someone suggest the pseudocode for the body of this function to get the correct resulting change to minimize the resulting number of coins? Optimization would be nice to, but first how to get it working? I'm really stuck here. Here I've written the starting code in C++, but the problem is language-independent.

#include <iostream>
#include <array>
#include <algorithm>

enum CoinType {A, B, C, D, E, NumCoinTypes};

struct Currency {
    std::array<int, NumCoinTypes> coins;
    Currency (int a, int b, int c, int d, int e) : coins ({a,b,c,d,e}) {}
    void print() const {
        for (int x : coins) std::cout << x << ' ';
        std::cout << "  total coins = " << std::accumulate (coins.begin(), coins.end(), 0) << '\n';
    }
};

struct Item {
    struct Value { int numCoins;  CoinType coinType; };
    Value value;
};

template <int AtoE, int BtoE, int CtoE, int DtoE>
void purchase (int numCoins, CoinType coinType, int a, int b, int c, int d, int e) {
    const Item item {numCoins, coinType};
    Currency currency(a,b,c,d,e);
    std::cout << "Before paying for the item: ";  currency.print();
    // Goal:  Purchase 'item' so that the change in 'currency' due to paying for 'item'
    // and receiving the change minimizes the number of coins in 'currency'.
    // Modify 'currency' somehow here.


    std::cout << "After paying for the item: ";  currency.print();
}

int main() {
    purchase<5,10,8,15>(50, C, 1,2,5,40,30);  // Sample test run.
}

There have been some references to the Knapsack Problem, but I'm not sure it applies here. The amount of money S that is given to the cashier is not known. Thus the change received, which is S - price, is not fixed, so it does not appear to me that the knapsack problem applies. Perhaps, once could try all possible (reasonable) values of S and then apply a Knapsack algorithm to each S value. But the amount of change comprising the currency not given to the cashier also depends on what S was (and the currency used to hand over the amount S). The amount of coins being minimized is not just that which adds up to S - price, but rather ALL the coins, including those not given to the cashier (which, again, depends on S and the currency to make up S). Also, the number of coins for each coin type in the result is not just 1 or 0.

Update: Thanks to Edward Doolittle's algorithm, the problem has been solved (my implemented code in one the answers below), but the solution makes one assumption: that the customer pays for the item with ALL the coins he possesses. Mathematically, the optimized change does give the correct answer, but it doesn't simulate the real world too well. Would a customer carrying a huge bag of change really pour out ALL his change to buy a candy???

So now I stipulate a condition that will seek a second solution. This second solution will not minimize the resulting number of coins like the first solution, but it does give a more realistic result. This new condition is:

The customer shall pay for the item with some of his coins such that he pays enough to purchase the item without paying any redundant coins.

For example, if 4 quarters is enough to purchase the item, he shall NOT pay a 5th quarter (nor shall he add any pennies or whatever on top of these 4 quarters). This condition is pretty much what the typical customer in the real world follows when purchasing an item. So here is the algorithm I've thought of for determining what coins the customer shall pay to minimize his number of coins at the end while following the above condition: The total payment will be with as many of the cheapest coins as possible, then (if these are not enough), with as many of the second cheapest coin as possible, then (if these are also not enough), with as many of the third cheapest coin as possible, and so forth. However, I'm not sure if this is the correct algorithm, and even if it is, it needs mathematical proof. I've written a solution using this algorithm and provided it as another answer.

Answer 1

Second solution which follows this new condition (to simulate the real world better):

The customer shall pay for the item with some of his coins such that he pays enough to purchase the item without paying any redundant coins.

For example, if 4 quarters is enough to purchase the item, he shall NOT pay a 5th quarter (nor shall he add any pennies or whatever on top of these 4 quarters).

The algorithm I used: The total payment will be with as many of the cheapest coins as possible, then (if these are not enough), with as many of the second cheapest coin as possible, then (if these are also not enough), with as many of the third cheapest coin as possible, and so forth. However, I'm not sure if this is the correct algorithm, and even if it is, it needs mathematical proof.

This time I found it more convenient to arrange the coin values from least valuable to most valuable.

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>

enum CoinType {A, B, C, D, E};  // Coins are arranged from the least valuable to the most valuable.

template <std::size_t NumCoinTypes>
struct Currency {
    std::array<int, NumCoinTypes> coins;
    template <typename... Args>
    Currency (Args&&... args) : coins ({std::forward<Args>(args)...}) {}
    void addCoins (const std::array<int, NumCoinTypes>& coinsAdded) {
        for (std::size_t i = 0;  i < NumCoinTypes;  i++)
            coins[i] += coinsAdded[i];
    }
    void deductCoins (const std::array<int, NumCoinTypes>& coinsDeducted) {
        for (std::size_t i = 0;  i < NumCoinTypes;  i++)
            coins[i] -= coinsDeducted[i];
    }
    void print() const {
        for (int x : coins) std::cout << x << ' ';
        std::cout << "(total coins = " << std::accumulate (coins.begin(), coins.end(), 0) << ")\n";
    }
};

template <int... CoinValues>
std::array<int, sizeof...(CoinValues)> optimizedChange (int change) {
    const std::size_t N = sizeof...(CoinValues);
    static const std::array<int, N> coinValues = {CoinValues...};
    std::vector<int> n(change+1);  // For each i = 0, 1, ..., change-1, n[i] represents the minimum number of coins needed to make change for value i.
    n[0] = 0;
    n[1] = 1;  // Since the cheapest coin has value 1.
    for (int i = 2; i <= change; i++) {
        std::vector<int> candidates;
        for (int c : coinValues)
            if (c <= i)
                candidates.push_back (n[i-c] + 1);  // 1 coin of value c + the minimum number of coins to get value i-c.
        n[i] = *std::min_element (candidates.begin(), candidates.end());
    }
    std::array<int, N> changeGiven = {0};  // With n[change] computed, we now compute changeGiven, where changeGiven[i] is the number of the ith coin in the optimized change (0th being the first).
    int v = change;
    while (v > 0) {
        for (int i = 0; i < N; i++) {
            if (coinValues[i] > v)
                continue;
            if (n[v - coinValues[i]] < n[v]) {
                changeGiven[i]++;
                v -= coinValues[i];
                continue;
            }
        }
    }
    return changeGiven;
}

template <std::size_t CoinType, std::size_t N>
int totalAmountHelper (const std::array<int, N>&) {
    return 0;
}

template <std::size_t CoinType, std::size_t N, int First, int... Rest>
int totalAmountHelper (const std::array<int, N>& coins) {
    return coins[CoinType] * First + totalAmountHelper<CoinType + 1, N, Rest...>(coins);
}

template <std::size_t N, int... CoinValues>
int totalAmount (const std::array<int, N>& coins) {
    return totalAmountHelper<0, N, CoinValues...>(coins);
}

template <std::size_t CoinType, std::size_t N, int Last>  // Here we assume there is enough to pay for the item with this last (most valuable) coin type.
std::array<int, N> totalPaymentHelper (std::array<int, N>& coins, int price, int) {
    if (price % Last == 0) {
        coins[CoinType] = price / Last;
        return coins;
    }
    coins[CoinType] = price / Last + 1;
    return coins;
}

// The total payment will be with as many of the cheapest coins as possible, then (if these are not enough), with as many as the second cheapest coin possible, and so forth.
template <std::size_t CoinType, std::size_t N, int First, int... Rest, typename... Args>
std::array<int, N> totalPaymentHelper (std::array<int, N>& coins, int price, int first, Args... rest) {
    if (price / First <= first) {
        if (price % First == 0) {
            coins[CoinType] = price / First;  // Exactly enough to pay the price.
            return coins;  // There shall be no change.
        }
        if (price / First < first) {
            coins[CoinType] = price / First + 1;  // One extra coin must be paid.
            return coins;  // There will be some change.
        }
    }
    const int totalFromFirst = first * First;
    coins[CoinType] = first;
    return totalPaymentHelper<CoinType + 1, N, Rest...>(coins, price - totalFromFirst, rest...);
}

template <int... CoinValues, typename... Args>
std::array<int, sizeof...(Args)> totalPayment (int price, Args&&... args) {
    const std::size_t N = sizeof...(Args);
    std::array<int, N> coins = {0};
    return totalPaymentHelper<0, N, CoinValues...>(coins, price, std::forward<Args>(args)...);
}

template <int... CoinValues, typename... Args>
void purchase (int numCoins, CoinType coinType, Args&&... args) {  // price = numCoins * coinType's value
    const std::size_t N = sizeof...(CoinValues);
    Currency<N> currency(std::forward<Args>(args)...);
    std::cout << "Before paying for the item, currency possessed is: ";  currency.print();
    static const std::array<int, N> coinValues = {CoinValues...};
    const int price = numCoins * coinValues[coinType];
    const std::array<int, N> coinsPaid = totalPayment<CoinValues...>(price, std::forward<Args>(args)...);
    currency.deductCoins (coinsPaid);
    const int totalPaid = totalAmount<N, CoinValues...>(coinsPaid);
    const int change = totalPaid - price;
    const std::array<int, N> coinsReturned = optimizedChange<CoinValues...>(change);
    currency.addCoins (coinsReturned);
    std::cout << "Price of item = " << price << '\n';
    std::cout << "Coins paid: ";  for (int x : coinsPaid) std::cout << x << ' ';  std::cout << '\n';
    std::cout << "Total amount paid = " << totalPaid << '\n';
    std::cout << "Total change = " << change << '\n';
    std::cout << "Coins returned as change: ";  for (int x : coinsReturned) std::cout << x << ' ';  std::cout << '\n';
    std::cout << "After paying for the item, currency possessed is: ";  currency.print();
}

int main() {
    std::cout << "Value of each coin: 1, 10, 25, 50, 100\n";
    purchase<1,10,25,50,100>(151, A, 30,4,5,2,1);
}

Output:

Value of each coin: 1, 10, 25, 50, 100
Before paying for the item, currency possessed is: 30 4 5 2 1 (total coins = 42)
Price of item = 151
Coins paid: 30 4 4 0 0
Total amount paid = 170
Total change = 19
Coins returned as change: 9 1 0 0 0
After paying for the item, currency possessed is: 9 1 1 2 1 (total coins = 14)

But I'm not sure if this is mathematically the correct solution though (while following the new condition). The 9 pennies as change looks suspicious to me.

I'm considering writing a third solution that by brute force tries all possible coin payments (that obey the condition above). This will certainly be slower, but it will at least give the correct answer and, more importantly, tell me if the solution above is mathematically correct or not.

Update: I finished writing the brute-force 3rd solution. It has proven that the above algorithm does NOT give the optimal solution. Instead, the brute force solution yields an optimal payment of 25 0 5 0 0 (equalling an exact total of 151), and the resulting coins after receiving the optimal change (which is no change in this case) is 4 4 0 2 1, with a total of 11 coins instead of 14. This brute force method narrowed it down to 37 possible payments that meet the new condition, with only one that resulted in 11 coins at the end (already described above). So this 3rd solution seems to be the only correct solution to this new problem (with this new condition), but the time complexity looks shabby, so I want to see if I can improve its time complexity before I post it.

Ok, here is my third and final solution. It looks correct to me now. Anyone who can think of improving its time complexity, feel free to chime in, but I followed the dynamic programming method of Edward Doolittle.

http://ideone.com/A1nUD2

Answer 2

Credit goes to Edward Doolittle for his algorithm and to Hurkyl for suggesting how to compute the change.

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>

enum CoinType {A, B, C, D, E};  // Can always add more.

template <std::size_t NumCoinTypes>
struct Currency {
    std::array<int, NumCoinTypes> coins;
    template <typename... Args>
    Currency (Args&&... args) : coins ({std::forward<Args>(args)...}) {}
    void print() const {
        for (int x : coins) std::cout << x << ' ';
        std::cout << "  total coins = " << std::accumulate (coins.begin(), coins.end(), 0) << '\n';
    }
};

template <int... CoinValues>
std::array<int, sizeof...(CoinValues)> optimizedChange (int change) {
    const int N = sizeof...(CoinValues);
    static const std::array<int, N> coinValues = {CoinValues...};
    std::vector<int> n(change+1);  // For each i = 0, 1, ..., change-1, n[i] represents the minimum number of coins needed to make change for value i.
    n[0] = 0;
    n[1] = 1;  // Since the cheapest coin has value 1.
    for (int i = 2; i <= change; i++) {
        std::vector<int> candidates;
        for (int c : coinValues)
            if (c <= i)
                candidates.push_back (n[i-c] + 1);  // 1 coin of value c + the minimum number of coins to get value i-c.
        n[i] = *std::min_element (candidates.begin(), candidates.end());
    }
    std::array<int, N> changeGiven = {0};  // With n[change] computed, we now compute changeGiven, where changeGiven[i] is the number of the ith coin in the optimized change (0th being the first).
    int v = change;
    while (v > 0) {
        for (int i = 0; i < N; i++) {
            if (coinValues[i] > v)
                continue;
            if (n[v - coinValues[i]] < n[v]) {
                changeGiven[i]++;
                v -= coinValues[i];
                continue;
            }
        }
    }
    return changeGiven;
}

template <int Last>
int totalPayment (int last) {
    return last * Last;
}

template <int First, int... Rest, typename... Args>
int totalPayment (int first, Args... rest) {
    return first * First + totalPayment<Rest...>(rest...);
}

template <int... CoinValues, typename... Args>
void purchase (int numCoins, CoinType coinType, Args&&... args) {  // price = numCoins * coinType's value
    const int N = sizeof...(CoinValues);
    Currency<N> currency(std::forward<Args>(args)...);
    std::cout << "Before paying for the item, currency possessed is: ";  currency.print();
    static const std::array<int, N> coinValues = {CoinValues...};
    const int price = numCoins * coinValues[coinType];
    std::cout << "Price of item = " << price << '\n';
    const int change = totalPayment<CoinValues...>(std::forward<Args>(args)...) - price;
        // Simply pay with ALL the coins possessed.  The optimized change is the answer.
    std::cout << "Total change = " << change << '\n';
    currency.coins = optimizedChange<CoinValues...>(change);  // The main line!
    std::cout << "After paying for the item, currency possessed is: ";  currency.print();
}

int main() {
    purchase<100,50,25,10,1>(3, B, 1,2,5,40,30);
}

Output:

Before paying for the item, currency possessed is: 1 2 5 40 30   total coins = 78
Price of item = 150
change = 605
After paying for the item, currency possessed is: 5 1 1 3 0   total coins = 10 
    (note that 6 0 0 0 5 would give 11 coins instead)

Answer 3

You're actually making the problem harder than it needs to be: just pay with all of your coins, then receive optimal change. This will always give the optimal result.

Once you know the result, then if you're so inclined, you can normalize the transaction so you don't both pay and receive a type of coin.

So really, what you need to do is to determine how much money you will have after the transaction, and make that amount of money in as few coins as possible.

Your original version (A is an integer multiple of the value of B, B is an integer multiple of the value of C, and so on) actually has a trivial algorithm for producing optimal change, as described by Diogo: you use as many of the largest coin as you can.

Answer 4

If all the conversions are integers, and there is a least common measure which can be identified with 1 unit of value (it looks like your coin E would be such a thing), then the problem reduces to the classic change-making problem.

In North America we have 1 cent, 5 cent, 10 cent, 25 cent (ignoring higher valued coins). With that system, a greedy algorithm works: take the largest coin you can at each step. The result of that process is the minimum number of coins to make change. We say the system {1, 5, 10, 25} is canonical because the greedy algorithm works.

For other systems of coins, the greedy algorithm does not work. For example, if there are no 5 cent pieces, the greedy algorithm applied to 30 cents yields 25 + 1 + 1 + 1 + 1 + 1, six coins, whereas the minimum is 10 + 10 + 10, three coins. We say the system {1, 10, 25} is not canonical.

The simplest way to approach your problem is to set up a canonical system of coins, then just use the greedy algorithm. A simple canonical system is {1, 5, 10, 25} mentioned above. If you want something funkier you can use arithmetic progressions, geometric progressions, or Fibonacci numbers. Other examples and a general discussion can be found at http://arxiv.org/pdf/0809.0400.pdf.

If you want to use a non-canonical system, or if you want to use a system and can't prove that it's canonical, there's a dynamic programming solution. Let n[i] be an array from 0 to v, the amount for which you want to make change (e.g., in the example I gave above, v = 30). n[i] represents the minimum number of coins needed to make change for value i. We know n[0] = 0, and n[1] = 1 (because there is a 1 cent piece). Then we calculate the other n[i] in order. n[i] = min { n[i-c]+1 where c is a coin in the set}. So in the example {1, 10, 25}, we have n[2] = min {n[2-1]+1} = 2, n[3] = min {n[3-1]+1} = 3, n[4] = min{n[4-1]+1} = 4, ..., n[9] = 9, and n[10] = min {n[10-1]+1, n[10-10]+1} = min {10,1} = 1, ... . Once you have n[v], you work backwards, figuring out which coin c results in n[v-c] < n[v], and continue in that manner until you hit zero.

The dynamic programming solution is slower than the greedy algorithm ... much slower for large values v ... and it's more complicated to program and more error-prone. So I suggest you first check whether your system is canconical. If it isn't, you can change the system. If you are stuck with a non-canonical system in circulation, you can introduce new coin values to it to make it canonical. Then you can use the greedy algorithm.

Answer 5

Let's abstract out the real problem first:

Assume that there's a coin with value 1 (may not be one of a,b,c,d,e). After paying, the person is left with value=X (in #coins of value 1).

Now assume that conversions or AtoB / BtoC = AtoC.

Then the problem is a variant of knapsack: Fill bag of weight X with items of 5 types with weight Wa, Wb, ... using minimum items.

So even with the simplifications, the problem appears hard. But if you ignore the time complexity, the simple answer comes from Dynamic Programming. M(X) = Min(1 + M(X - wa), 1 + M(X - Wb), ...)

Answer 6

I didn't really understand your question. Why is there a CoinType field inside of the Item class?

If you want to minimize the amount of coins given as change, try coins that have the highest value first. Supose A is worth more than B:

coins_A = value_to_pay % value_coin_A;
value_to_pay -= coins_A * value_coin_A;
coins_B = value_to_pay % value_coin_B;
value_to_pay -= coins_B * value_coin_B;
// and so on