如何在C++中编程递归硬币更改？

Question

我想在C++中建立递归调用硬币更改。我在互联网上尝试了大部分算法，但它似乎不适用于矢量或者它没有使用硬币的总和。任何人都可以帮助我理解递归函数必须调用什么？所以我的算法没有给我使用的最小数量的硬币，我不知道如何保存使用的硬币。

int coin(vector<int> denom, int s,int N) 
{ 
    if(N == 0) 
    { 
     return 1; 
    } 
    if(N < 0 || (N > 0 && s < 0)) 
    { 
     return 0; 
    } 

    return min(coin(denom,s - 1, N), 1 + coin(denom, s,N-denom[s-1])); 

} 


Input a value N: 
    Input: 40 
Input how many denominations: 
    Input: 3 
Denominations #1: 
    Input: 5 
Denominations #2: 
    Input: 20 
Denominations #3: 
    Input: 30 

Output: 
Minimum # of coins: 2 
Coin used: 20 + 20 
Don't want: 30 + 5 + 5 

Answer 1

几点考虑：

• 首先，没有必要派教派的人数即s 作为参数传递给coin方法，只要一个vector正在被使用，因为vector内置size()方法，为我们做这项工作。
• 其次，保存液你需要的int命名solution另一个vector，但这vector只是造册，并没有任何实际递归实现，因此，它被定义为一个全局变量。或者，您也可以通过参考coin方法将它作为参数传递。
• 第三，在将用户输入的面额传递给coin方法之前，应对其进行排序。为此，我使用algorithm库中的sort方法。

什么递归算法基本上做的是：

• 在每一个步骤，它认为最大面额d（最后在排序面额元素vectordenom像denom[denom.size() - 1]），然后从vector使用去除pop_back方法vector。
• 使用d我们找到count_d，这是解决方案中使用的面额d的硬币数量。我们通过简单地应用像N/d这样的div操作得到这个，其给出商数。
• 然后d被添加到vectorsolution,count_d次数。
• 的递归调用，从该迭代增加count_d并回顾coin具有减小的面额vectordenom和使用N%d量N的剩余。

对什么的div /和国防部%运营商做清晰见Quotient and Remainder。

下面是代码：

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

vector<int> solution; 

int coin(vector<int> denom, int N) 
{ 
    if(N <= 0 || denom.size() <= 0) 
    { 
     return 0; 
    } 

    int d = denom[denom.size() - 1]; 
    denom.pop_back(); 

    int count_d = N/d; 

    solution.insert(solution.end(), count_d, d); 

    return count_d + coin(denom, N%d); 
} 

int main() 
{ 
    int N,s; 
    cout<<"Input a value N:\nInput: "; 
    cin>>N; 
    cout<<"Input how many denominations:\nInput: "; 
    cin>>s; 
    vector<int> denom; 

    for(int i = 0; i < s; i++) 
    { 
     int d; 
     cout<<"Denominations #"<<i+1<<":\nInput: "; 
     cin>>d; 
     denom.push_back(d); 
    } 

    std::sort(denom.begin(), denom.end()); 

    int minNoOfCoins = coin(denom, N); 

    cout<<"\nOutput:\nMinimum # of coins: "<<minNoOfCoins; 

    if(minNoOfCoins > 0) 
    { 
     cout<<"\nCoins used: "; 

     for(int i = 0; i < solution.size(); i++) 
     { 
      if(i > 0) 
      { 
       cout<<" + "; 
      } 
      cout<<solution[i]; 
     } 
    } 

    cout<<endl; 

    system("pause"); 
}