如何在硬币找零问题中添加有限的硬币？ （自下而上 - 动态规划）

Question

我是动态编程的新手（和C++，但我有更多的经验，有些事情我仍然不知道）。如何将有限硬币添加到硬币找零问题（请参阅下面的代码 - 有点混乱，但我仍在研究它）。我有一个变量 nr[100] 来记录硬币的数量（还在我的 read_values() 中创建了一些条件）。我不知道在我的代码中哪里可以使用它。

该代码认为我们有无限的硬币供应（我不希望这样）。 它是用自下而上的方法（动态规划）制定的。

我的代码受到以下视频的启发：Youtube

#include <iostream>
using namespace std;
int C[100], b[100], n, S, s[100], nr[100], i, condition=0, ok=1;

void read_values() //reads input
{   
    cin >> n; // coin types
    cin >> S; // amount to change
    
    for (i=1; i<=n; i++)
    {
        cin >> b[i]; //coin value
        cin>>nr[i]; //coin amount
        if(nr[i]==0)b[i]=0; //if there are no coin amount then the coin is ignored
        
        condition+=b[i]*nr[i]; //tests to see if we have enough coins / amount of coins to create a solution
        if(b[i]>S)
        {
            b[i]=0;
        }
    }

    if(S>condition)
    {
        cout<<endl;
        cout<<"Impossible!";
        ok=0;
    }
}
void payS()
{
    int i, j;
    C[0] = 0; // if amount to change is 0 then the solution is 0
    for (j=1; j<=S; j++) 
    {
        C[j] = S+1;
        for (i=1; i<=n; i++)
        {

            if (b[i] <= j && 1 + C[j - b[i]] < C[j])
            {
                C[j] = 1 + C[j - b[i]]; 
                s[j] = b[i];
            }

        }
    }
    cout << "Minimum ways to pay the amount: " << C[S] << endl;
}

void solution(int j)
{
    if (j > 0)
    {
        solution(j - s[j]);
        cout << s[j] << " ";
    }
}
int main()
{

    read_values();
    if(ok!=0)
    {
        payS();
        cout << "The coins that have been used are: ";
        solution(S);
    }
}

Answer 1

我假设您需要使用 nbr 表生成正整数值 amount 的找零，其中 nbr[n]是价值n的可用硬币数量。我还假设 nbr[0] 实际上毫无意义，因为它只代表没有价值的硬币。

大多数动态规划问题通常都是在选择选项 A 与选项 B 的二元决策上递归。通常，一个选项是“选择这个”，另一个选项是“不选择这个并使用可用集合的其余部分”。这个问题确实没有什么不同。

首先，我们来解决没有缓存的递归动态问题。

我将用名为 “cointable” 的数据结构替换您的 nbr 变量。这用于跟踪可用的硬币集和为任何给定解决方案路径选择的硬币集：

struct cointable
{
    static const int MAX_COIN_VALUE = 100;
    int table[MAX_COIN_VALUE+1]; // table[n] maps "coin of value n" to "number of coins availble at amount n"
    int number; // number of coins in table
};

cointable::table 实际上与您的 nbr 数组。 coinbase::number 是表中值的总和。它不用于跟踪可用硬币，但用于跟踪更好的解决方案。

现在我们可以介绍没有查找缓存的递归解决方案。

递归的每个步骤都会执行以下操作：

1. 在可用硬币集合中查找不大于要解决的目标金额的最高价值的硬币

2. 递归选项 A：选择从步骤 1 中选择的该硬币。现在使用以下方法（递归地）解决减少的金额减少了可用硬币的数量。

3. 递归选项 B：不要选择这枚硬币，而是递归使用比步骤 1 中找到的价值更低的第一个硬币。

4. 比较 2 和 3 的递归结果。选择硬币数量较少的硬币使用过

这是代码 - 不使用最佳查找缓存

bool generateChange(int amount, cointable& available, cointable& solution, int maxindex)
{
    if ((maxindex == 0) || (amount < 0))
    {
        return false;
    }

    if (amount == 0)
    {
        return true;
    }

    int bestcoin = 0;

    // find the highest available coin that not greater than amount
    if (maxindex > amount)
    {
        maxindex = amount;
    }

    // assert(maxindex <= cointable::MAX_COIN_VALUE)

    for (int i = maxindex; i >= 1; i--)
    {
        if (available.table[i] > 0)
        {
            bestcoin = i;
            break;
        }
    }

    if (bestcoin == 0)
    {
        return false; // out of coins
    }

    // go down two paths - one with picking this coin.  Another not picking it

    // option 1
    // pick this coin (clone available and result)
    cointable a1 = available;
    cointable r1 = solution;
    a1.table[bestcoin]--;
    r1.table[bestcoin]++;
    r1.number++;
    bool result1 = generateChange(amount - bestcoin, a1, r1, bestcoin);

    // option2 - don't pick this coin and start looking for solutions with lesser 
    // coins (not the use of references for a2 and r2 since we haven't changed anything)

    cointable& a2 = available;
    cointable& r2 = solution;
    bool result2 = generateChange(amount, a2, r2, bestcoin - 1);

    bool isSolvable = result1 || result2;

    if (!isSolvable)
    {
        return false;
    }

    // note: solution and r2 are the same object, no need to reassign solution=r2
    if (
        ((result1 && result2) && (r1.number < r2.number))
        || (result2 == false)
        )
    {
        solution = r1;
    }

    return true;
}

然后快速演示如何计算 128 美分的零钱，给定较大硬币数量有限教派：{1:100, 5:20, 10:10, 25:1, 50:1}

int main()
{
    cointable available = {};  // zero-init
    cointable solution = {};   // zero-init

    available.table[1] = 100;
    available.table[5] = 20;
    available.table[10] = 10;
    available.table[25] = 1;
    available.table[50] = 1;
    int amount = 128;

    bool result = generateChange(amount, available, solution, cointable::MAX_COIN_VALUE);

    if (result == true)
    {
        for (int i = 1; i < 100; i++)
        {
            if (solution.table[i] > 0)
            {
                std::cout << i << " : " << solution.table[i] << "\n";
            }
        }
    }
    else
    {
        cout << "no solution\n";
    }
}

这应该有效。对于大多数人来说，对于一美元以下的零钱来说，它可能已经足够快了，因此不需要缓存。所以我们有可能就在这里停下来并完成。

我要在这里停下来

我开始研究一种引入“缓存”以避免冗余递归的解决方案。但在对其进行基准测试并研究算法如何快速找到最佳解决方案之后，我不太确定缓存是否必要。我最初尝试为可解和不可解的解决方案插入缓存表，只是使代码变慢。我需要研究如何让它发挥作用——如果有必要的话。

Answer 2

也许您希望我们修复您的代码，但我实现了我自己的解决方案版本。希望我自己的版本对你有用，至少在教育上。

当然，我使用了动态编程方法。

我保留了可能进行更改的向量。接下来的每个金额都是由之前的金额加上几个相同价值的硬币组成的。

使用过的硬币的历史也被保留，这使我们能够将每次更改恢复为精确给定硬币的组合。

在代码之后，您可以看到控制台输出，其中显示了用硬币 2x4、3x3、5x2、10x1 组成找零 13 的示例（这里第二个数字是硬币数量）。

输入硬币及其数量在 main() 函数开始处的 coins 向量内给出，您可以用您想要的任何内容填充此向量，例如通过控制台用户输入。需要表示的更改在变量 change 内给出。

不要忘记在代码和控制台输出之后查看 Post Scriptum (PS.)，它有一些有关算法的更多详细信息。

完整代码如下：

在线尝试！

#include <cstdint>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <functional>
#include <iostream>

using u32 = uint32_t;
using u64 = uint64_t;

int main() {
    std::vector<std::pair<u32, u32>> const coins =
        {{2, 4}, {3, 3}, {5, 2}, {10, 1}};

    u32 const change = 13;

    std::vector<std::unordered_map<u32, std::pair<u64, std::set<u32>>>>
        sums = {{{0, {1, {}}}}};

    for (auto [coin_val, coin_cnt]: coins) {
        sums.push_back({});
        for (auto const & [k, v]: sums.at(sums.size() - 2))
            for (size_t icnt = 0; icnt <= coin_cnt; ++icnt) {
                auto & [vars, prevs] = sums.back()[k + coin_val * icnt];
                vars += v.first;
                prevs.insert(icnt);
            }
    }
    std::vector<std::pair<u32, u32>> path;
    std::vector<std::vector<std::pair<u32, u32>>> paths;
    std::function<bool(u32, u32, u32)> Paths =
        [&](u32 sum, u32 depth, u32 limit){
            if (sum == 0) {
                paths.push_back(path);
                std::reverse(paths.back().begin(), paths.back().end());
                return paths.size() < limit;
            }
            auto const coin = coins.at(depth - 1).first;
            auto const & [_, prevs] = sums.at(depth).at(sum);
            for (auto const cnt: prevs) {
                if (cnt > 0)
                    path.push_back({coin, cnt});
                if (!Paths(sum - coin * cnt, depth - 1, limit))
                    return false;
                if (cnt > 0)
                    path.pop_back();
            }
            return true;
        };

    if (!sums.back().count(change)) {
        std::cout << "Change " << change
            << " can NOT be represented." << std::endl;
        return 0;
    }
    std::cout << "Change " << change << " can be composed "
        << std::get<0>(sums.back().at(change)) << " different ways." << std::endl;
    Paths(change, coins.size(), 20);
    std::cout << "First " << paths.size() << " variants:" << std::endl;
    for (auto const & path: paths) {
        std::cout << change << " = ";
        for (auto [coin, cnt]: path)
            std::cout << coin << "x" << cnt << " + ";
        std::cout << std::endl;
    }
}

输出：

Change 13 can be composed 5 different ways.
First 5 variants:
13 = 2x2 + 3x3 + 
13 = 2x4 + 5x1 + 
13 = 2x1 + 3x2 + 5x1 + 
13 = 3x1 + 5x2 + 
13 = 3x1 + 10x1 + 

PS. 如您所愿注意到，算法的主要动态编程部分非常小，只有以下几行：

    std::vector<std::unordered_map<u32, std::pair<u64, std::set<u32>>>>
        sums = {{{0, {1, {}}}}};

    for (auto [coin_val, coin_cnt]: coins) {
        sums.push_back({});
        for (auto const & [k, v]: sums.at(sums.size() - 2))
            for (size_t icnt = 0; icnt <= coin_cnt; ++icnt) {
                auto & [vars, prevs] = sums.back()[k + coin_val * icnt];
                vars += v.first;
                prevs.insert(icnt);
            }
    }

该部分保留所有当前可组合的总和（更改）。算法从 0 的货币变化开始，然后将 1×1 硬币增量添加到所有可能的当前变化（总和）中，从而形成新的总和（包括这个新硬币）。

每个总和都保留了一个计数器，其中包含所有可能的组成方式，并且它还跟踪导致该总和的所有最后硬币。最后一组硬币允许进行回溯，以恢复硬币的具体组合，而不仅仅是计算该总和的方法的数量。