Geek Answers Handbook

Minimizing the number of coins after purchasing a product

I came up with this algorithmic problem, trying to solve the problem in my (adventure) program. There are 5 different types of coins called A, B, C, D, E (from the most valuable to the least valuable). Conversions between coin values ​​are AtoE, BtoE, CtoE, DtoE (that is, AtoE means that a coin of type A costs AtoE to multiply by a value a coin of type E). The structure Currencyrepresents how much money the client has. Function Purpose

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)

must have the client (which atype of coins a, bcoin-type b, etc.)) to buy the item, the price numCoins coinType, while minimizing the number of coins, which he received after the receipt of the change. Can someone suggest a pseudo-code for the body of this function to get the right change in order to minimize the resulting number of coins? Optimization would be nice, but first, how to make it work? I am really stuck here. Here I wrote the source code in C ++, but the problem does not depend on the language.

#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.
}

Knapsack, , . S, , . , S - price , , . , () S, Knapsack S. , , , , S ( S). - , S - price, , , ( S S). , 1 0.

: ( ), : , . , . , , , ?

, , . , , . :

, , , .

, 4 , 5- ( , - ). . , , , , , , : , ( ), , ( ), .. , , , . , , .

+4
6

, , 1 (, E ), .

1 , 5 , 10 , 25 ( ). : , . . , {1, 5, 10, 25} , .

. , 5 , , 30 , 25 + 1 + 1 + 1 + 1 + 1, , 10 + 10 + 10, . , {1, 10, 25} .

- , . (1, 5, 10, 25) . - , , . http://arxiv.org/pdf/0809.0400.pdf.

, , . n[i] - 0 v, , (, , v = 30). n[i] , i. n[0] = 0 n[1] = 1 ( 1 ). n[i] . n[i] = min { n[i-c]+1 where c is a coin in the set}. , {1, 10, 25} 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 n[10] = min {n[10-1]+1, n[10-10]+1} = min {10,1} = 1,.... n[v], , , c n[v-c] < n[v], , .

, ... v... . , . , . , , . .

+4

, : , . .

, , , , .

, , , , .

(A , B, B , C ..), , Diogo: .

+2

. Item CoinType?

, , . , A , 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
+1

:

, 1 ( a, b, c, d, e). = X ( #coins 1).

, AtoB/BtoC = AtoC.

: X 5 Wa, Wb,... .

, . , . M (X) = Min (1 + M (X - wa), 1 + M (X - Wb),...)

+1

Hurkyl .

#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 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);
}

:

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)
0

, ( ):

, , , .

, 4 , 5- ( , - 4 ).

: , ( ), , ( ), .. , , , .

.

#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 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);
}

:

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)

, , ( ). 9 .

, ( ). , , , , , , , , .

Update: . , . 25 0 5 0 0 ( 151), ( ) 4 4 0 2 1, 11 14. 37 , , , 11 ( ). , 3- , , ( ), , , , .

Well, here is my third and final decision. Now it looks right. Anyone who might think of improving their time complexity, feel free to call, but I followed the dynamic programming method of Edward Doolitt.

http://ideone.com/A1nUD2

0
source

More articles:


All Articles