购买物品后最小化硬币数量-Java 学习之路

在尝试解决我的（基于冒险的）程序中的问题时，我想出了这个算法问题 . 有5种不同类型的硬币，分别称为A，B，C，D，E（从最有 Value 到最有 Value ） . 硬币值之间的转换是AtoE，BtoE，CtoE，DtoE（即AtoE意味着A型硬币值AtoE乘以E型硬币的值） . struct Currency 表示客户有多少钱 . 该功能的目标

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)

是让客户（谁有 A 的 a 硬币， B 类型的 b 硬币......等）购买价格为 numCoins coinType s的商品，同时尽量减少收到更改后的硬币数量 . 有人可以建议这个函数的主体的伪代码来获得正确的结果更改，以最小化硬币的结果数量？优化会很好，但首先如何让它工作？我已经用C编写了起始代码，但问题与语言无关 .

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

有一些关于背包问题的参考，但我不确定它是否适用于此 . 提供给收银员的金额S是未知的 . 因此，收到的更改，即 S - price ，并不固定，因此我认为背包问题不适用 . 也许，曾经可以尝试S的所有可能（合理）值，然后对每个S值应用Knapsack算法 . 但是，包括未给出纳员的货币的变化量也取决于S是什么（以及用于交出金额S的货币） . 最小化的硬币数量不仅仅是加起来的金额，而是所有硬币，包括那些没有给出纳员的硬币（再次，它取决于S和货币来组成S） . 此外，结果中每种硬币类型的硬币数量不仅仅是1或0 .

Update: 感谢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模拟现实世界 . 携带巨大变化的顾客真的会倾诉他所有的变化来购买糖果吗？

所以现在我规定了一个寻求第二种解决方案的条件 . 第二种解决方案不会像第一种解决方案那样最小化硬币产生的数量，但它确实给出了更真实的结果 . 这个新条件是：

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.

例如，如果4个季度足以购买该物品，则他不应支付第5个季度（也不应在这4个季度之外添加任何便士或其他任何东西） . 这种情况几乎是现实世界中典型客户在购买商品时所遵循的条件 . 所以这里是我想到的算法，用于确定客户应该支付哪些硬币，以便在遵循上述条件时最小化他的硬币数量：总支付将使用尽可能多的最便宜的硬币，然后（如果这些还不够），尽可能多的第二个最便宜的硬币，然后（如果这些还不够），尽可能多的第三个最便宜的硬币，等等 . 但是，我不确定这是否是正确的算法，即使它是，它也需要数学证明 . 我已经使用这种算法编写了一个解决方案并将其作为另一个答案 .

6 回答

2

如果所有的转换都是整数，并且有一个最不常见的度量可以用1个单位的 Value 来识别（看起来你的硬币E会是这样的事情），那么问题就会减少到经典的变革问题 .

在北美，我们有1美分，5美分，10美分，25美分（忽略更高 Value 的硬币） . 使用该系统，贪婪算法可以工作：在每一步中获取最大的硬币 . 该过程的结果是进行更改的最小硬币数量 . 我们说系统{1,5,10,25}是 canonical 因为贪婪算法有效 .

对于其他硬币系统，贪婪算法不起作用 . 例如，如果没有5美分，则应用于30美分的贪心算法产生25 1 1 1 1 1，六个硬币，而最小值为10 10 10，三个硬币 . 我们说系统{1,10,25}不是规范的 .

解决问题的最简单方法是 Build 一个规范的硬币系统，然后只使用贪心算法 . 一个简单的规范系统是上面提到的{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] ，你就可以向后工作，找出 n[v-c] < n[v] 中的哪一枚硬币，然后以这种方式继续，直到你达到零 .

动态编程解决方案比贪婪算法慢......对于大值 v 而言要慢得多......它可以改变系统 . 如果您在流通中遇到非规范系统，您可以为其引入新的硬币值以使其成为规范 . 然后你可以使用贪心算法 .

回复于 2024-04-28T01:53:45+08:00
0

你实际上使问题变得比它需要的更难：只需用你所有的硬币支付，然后获得最佳的改变 . 这将始终提供最佳结果 .

一旦你知道结果，那么如果你这么倾向，你就可以规范化交易，这样你就不会同时支付和收到一种硬币 .

所以，你需要做的就是确定交易后你将获得多少钱，并尽可能少地使用这些钱 .

您的原始版本（ A 是 B 的值的整数倍， B 是 C 的整数倍，依此类推）实际上有一个简单的算法用于产生最佳更改，如_1034769所述：您使用尽可能多的你可以买到最大的硬币 .

回复于 2024-04-28T01:53:45+08:00
0
我真的不明白你的问题 . 为什么在Item类中有CoinType字段？

如果您想最小化作为更改的硬币数量，请先尝试具有最高 Value 的硬币 . Supose 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
```
回复于 2024-04-28T01:53:45+08:00
1

让我们首先抽象出真正的问题：

假设有一个值为1的硬币（可能不是a，b，c，d，e之一） . 支付后，该人留下值= X（在值为＃的#coins中） .

现在假设转换或AtoB / BtoC = AtoC .

然后问题是背包的变种：用重量为W，Wb，...的5种类型的物品填充重量X的袋子，使用最少的物品 .

因此即使简化，问题也很难解决 . 但如果忽略时间复杂性，简单的答案来自动态编程 . M（X）= Min（1M（X-wa），1M（X-Wb），...）

回复于 2024-04-28T01:53:45+08:00

感谢Edward Doolittle的算法和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'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);
}

输出：

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)

回复于 2024-04-28T01:53:45+08:00

遵循这个新条件的第二个解决方案（更好地模拟现实世界）：

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.

例如，如果4个季度足以购买该物品，则他不应支付第5个季度（也不应在这4个季度之外添加任何便士或其他任何东西） .

我使用的算法：总付款将使用尽可能多的最便宜的硬币，然后（如果这些还不够），尽可能多的第二便宜的硬币，然后（如果这些还不够），与尽可能多的第三便宜的硬币，等等 . 但是，我不确定这是否是正确的算法，即使它是，它也需要数学证明 .

这一次，我发现将硬币值从最不重要的 Value 安排到最有 Value 的价格更方便 .

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

输出：

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: 我写完了蛮力第3解决方案 . 已经证明上述算法没有给出最优解 . 相反，蛮力解决方案产生 25 0 5 0 0 （等于确切总数151）的最佳支付，并且在收到最佳变化（在这种情况下没有变化）之后产生的硬币是 4 4 0 2 1 ，总共11个硬币而不是14.这种蛮力方法将其缩小到37种可能的付款，以满足新条件，只有一种最终产生了11个硬币（已在上文中描述） . 因此，第三个解决方案似乎是解决这个新问题的唯一正确解决方案（使用这个新条件），但时间复杂度看起来很简陋，所以我想看看我是否可以在发布之前改进其时间复杂度 .

好的，这是我的第三个也是最后一个解决方案现在看起来对我来说是正确的 . 任何能够提高其时间复杂度的人都可以随意插入，但我遵循了Edward Doolittle的动态编程方法 .

http://ideone.com/A1nUD2

回复于 2024-04-28T01:53:45+08:00

购买物品后最小化硬币数量

6 回答

相关问题