修改硬幣更改問題以跟蹤硬幣的使用情況（不是最小數量）

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