c++ - 购买元素后最小化硬币数量

Question

我在尝试解决我的(基于冒险的)程序中的问题时想到了这个算法问题。有 5 种不同类型的硬币，分别称为 A、B、C、D、E(从最有值(value)到最不值钱)。之间的转换硬币值是 AtoE、BtoE、CtoE、DtoE(即 AtoE 表示 A 类型的硬币值 AtoE 乘以 a 的值E 型硬币)。结构 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 的硬币等...) 购买元素price 是 numCoins coinType，同时最小化他收到零钱后拥有的硬币数量。有人可以建议此函数主体的伪代码以获得正确的结果更改吗最小化由此产生的硬币数量？优化会很好，但首先如何让它工作？我真的被困在这里了。在这里，我用 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 值应用背包算法。但是包含未提供给收银员的货币的找零金额也取决于 S 是什么(以及用于交出金额 S 的货币)。被最小化的硬币数量不仅仅是加起来为 S - price 的硬币数量，而是所有硬币，包括那些没有给收银员的硬币(同样，这取决于 S 和货币)构成 S)。此外，结果中每种硬币类型的硬币数量不仅仅是 1 或 0。

更新:多亏了 Edward Doolittle 的算法，问题已经解决(我在下面的答案之一中实现了代码)，但解决方案做出了一个假设:客户用 ALL 为商品付款他拥有的硬币。从数学上讲，优化后的变化确实给出了正确的答案，但它并没有很好地模拟现实世界。一个背着一大袋零钱的顾客真的会倾其所有零钱去买一颗糖果吗？？？

所以现在我规定一个条件，会寻求第二个解决方案。第二种解决方案不会像第一种解决方案那样最大限度地减少所产生的硬币数量，但它确实会给出更真实的结果。这个新条件是:

客户应使用他的一些硬币支付商品，这样他就可以支付足够的钱来购买商品，而无需支付任何多余的硬币。

例如，如果 4 个季度足以购买该元素，则他无需支付第 5 个季度(也不得在这 4 个季度之上添加任何便士或其他任何东西)。这种情况几乎是现实世界中典型客户在购买商品时所遵循的情况。因此，这是我想到的算法，用于确定客户应支付哪些硬币以在满足上述条件的同时最大限度地减少他最后的硬币数量:总付款将使用尽可能多的最便宜的硬币，然后(如果这些还不够)，尽可能多地使用第二便宜的硬币，然后(如果这些也不够)，尽可能多地使用第三便宜的硬币，依此类推。但是，我不确定这是否是正确的算法，即使是，也需要数学证明。我已经使用该算法编写了一个解决方案并将其作为另一个答案提供。

Answer 1

如果所有的转换都是整数，并且有一个最不常见的度量可以用 1 个值(value)单位来标识(看起来你的硬币 E 就是这样的东西)，那么问题就简化为经典的找零问题。

在北美，我们有 1 美分、5 美分、10 美分、25 美分(忽略值(value)较高的硬币)。在这个系统中，贪婪算法起作用了:在每一步都拿走你能拿的最大的硬币。该过程的结果是要找零的最少硬币数量。我们说系统 {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 美分的一 block )。然后我们计算其他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 ...而且编程更复杂，更容易出错。所以我建议你先检查你的系统是否是canconical。如果不是，您可以更改系统。如果您被流通中的非规范系统所困，您可以为其引入新的硬币值(value)以使其成为规范系统。那么就可以使用贪心算法了。