修改硬币更改问题以跟踪硬币的使用情况（不是最小数量）

Question

我写了一个简单的硬币更改算法，该算法目前可以​​找到所需的硬币数量，以便与购买所需金额相匹配。我试图对它进行修改，以便跟踪每种面额的最小硬币数量，并且我会下降一点。所以，如果你将数字6传递给函数，它会说所需的最小硬币数量是2（我已经有这个数字），而且硬币的组合是4美分硬币和2分硬币。这里是我的代码：

coins[5] = {1, 2, 4, 17, 28} //effectively kills any use of greedy algortihms 
count[m]; 
int coins_needed_for(int m) { 


//Initilization- fills array w/ -1s 
for (int z = 1; z < m+1; z++) { 
    count[z] = -1;  
}//for 

//fills in appropriate values 
for (int j = 0; j < 5; j++) { 
    if (coins[j] < m) 
     count[coins[j]] = 1;  
    else if (coins[j] == 1) 
     return 1; 
    else 
     break; 
}//for 


//Execution 
for (int p = 1; p < m+1; p++) {  
    if (count[p] == -1) {   
     int min = 10000 //poor subsitute for infinity; 

     for (int i = 0; i < 5; i++) {    

      if (coins[i] <= p) {        
       if (count[p-coins[i]] + 1 < min) { 
        min = count[p-coins[i]] + 1;        
       }     
      }//if   
     count[p] = min;   
     }//for   
    }//if    
}//for 
return count[m]; 
} 

我明白需要什么，我只是不知道的最好的办法就是去这样做的。我应该创建另一个数组吗？如果是，它是否必须是二维的？我可以创建一个结构来保持每个硬币的计数用于每个可能的m吗？我愿意接受任何建议。我不一定在寻找一个明确的答案，只是指针和有用的建议。要求分配问题的答案是错误的。谢谢！

Answer 1

这是被称为一个非常古老的问题“更改决策问题。”看看Wikipedia要说些什么。

这是背包问题的一种形式，这不是一个小问题。

Answer 2

您可以使用除法和模量来简化操作。我会举一个例子。

 
afterQuarterTotal = totalAmount % 25; 
numberOfQuarters = (totalAmount - afterQuarterTotal)/25; 
afterDimeTotal = aftgerQuarterTotal % 10; 
numberOfDimes = (afterQuarterTotal - afterDimeTotal)/10; 

等等...

Answer 3

void recursive_program(int coins) 

{ 
    int times; 
    if (coins==0)             
      return; 

if (coins>=28)             
    {                
    times=coins/28; 
    cout<<times; 
    cout<<" * 28 for\t\t"<<times*28<<endl; 
    return recursive_program(coins%28); 
} 

if (coins>=17)             
{ 
    times=coins/17; 
    cout<<times; 
    cout<<" * 17 for\t\t\t "<<times*17<<endl; 
    return recursive_program(coins%17); 
} 

if (coins>=4)             
{ 
    times=coins/4; 
    cout<<times; 
    cout<<" * 4 for\t\t\t "<<times*4<<endl; 
    return recursive_program(coins%4); 
} 
if (coins>=2)             
{ 
    times=coins/2; 
    cout<<times; 
    cout<<" * 2 for\t "<<times*2<<endl; 
    return recursive_program(coins%2); 
} 

if (coins>=1)             
{ 
    times=coins/1; 
    cout<<times; 
    cout<<" * 1 for\t\t\t\t "<<times<<endl; 
    coins=0; 
    return recursive_program(coins); 
} 
} 

Answer 4

/* 硬币找零问题

输入规格： 第一个行预计 二线预计的硬币数量 第三行包含在面额 无限供给的硬币是的升序硬币量假设为

输出规格： 每种情况下都会显示最低面额的硬币，然后是最高的面额。 案件由线 分隔。如果无法找到和-1印

*/

#include<iostream> 
using namespace std; 
int *num,*coins,*maxC,n,amount,flag=0,stop=0; 
int sum() 
{ 
    int i=0,j; 
    int sum=0; 
    for(i=0;i<n;++i) 
     for(j=0;j<num[i];++j) 
      sum+=coins[i]; 
    return sum; 
} 
void print() 
{ 
    int i,j; 
    for(i=0;i<n;++i) 
    { 
     for(j=0;j<num[i];++j) 
      cout<<coins[i]<<" "; 
    } 
    cout<<endl; 
} 
void printNum() 
{ 
    int i; 
    for(i=0;i<n;++i) 
     cout<<num[i]<<" "; 
    cout<<endl; 
} 
void nextIter() 
{ 
    int i,j; 
    int stat=0; 
    //printNum(); //Remove the comment if you want to see the values of num array in every iteration 
    for(i=0;i<n;++i) 
    { 
     if(num[i]==0) 
      stat=1; 
     else 
     { 
      stat=0; 
      break; 
     } 
    } 
    if(stat) 
    { 
     stop=1; 
     return ; 
    } 
    for(i=n-1;i>=0;--i) 
    { 
     int dec=0; 
     if(num[i]==0) 
     { 
      dec=1; 
      num[i]=maxC[i]; 
     } 
     else 
     { 
      --num[i]; 
      return ; 
     } 
    } 
} 
int find() 
{ 
    while(!stop) 
    { 
     if(amount==sum()) 
     { 
      flag=1; 
      print(); 
     } 
     nextIter(); 
    } 
} 
int main() 
{ 
    int i; 
    cout<<"\nEnter amount:"; 
    cin>>amount; 
    cout<<"\nEnter number of coins:"; 
    cin>>n; 
    coins=new int[n]; 
    maxC=new int[n];//contains maximum number of each denomination required 
    num=new int[n];//contains current number of each denomination required 
    for(i=0;i<n;++i) 
    { 
     cin>>coins[i]; 
     num[i]=maxC[i]=amount/coins[i]; 
    } 
    find(); 
    if(!flag) 
     cout<<"-1"; 
    cout<<endl; 
    system("pause"); 
    return 0; 
}