台中女中程式解題系統：b028: 忙碌的超商店員

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b028。

此題用 Dynamic Programming 可參考網友 Chih-Yu Yeh 的說明文件：

換零錢問題換零錢問題 如何使用動態規劃(Dynamic Programming)來思考？

主要的演算法如下：

1.     for(int i = 0; i < 6; i++)    
2.     {    
3.         for(int j = cVal[i]; j <= n; j++)    
4.         {    
5.             // 若 目前面額 j 所需硬幣數大於 (目前面額 j 減去硬幣面額 cVal[i] 加 1 )    
6.             if( coin[j] > coin[j - cVal[i]] + 1 )    
7.                 coin[j] = coin[j - cVal[i]] + 1;    
8.         }    
9.     } 

程式碼：

1. /*  
2.  * 
3.  * coin[i] 目前面額 i 所需硬幣數  
4.  *  
5. */    
6. #include <iostream>    
7. #include <cstring>    
8.     
9. using namespace std;    
10.     
11. int main()    
12. {    
13.     int cVal[6] = {1, 5, 10, 12, 16, 20};    
14.     int coin[101];    
15.     
16.     // 將所需硬幣數全部設為100個    
17.     memset(coin, 100, sizeof(coin));    
18.     
19.     coin[0] = 0;    
20.     int n;    
21.     
22.     cin >> n;    
23.     
24.     for(int i = 0; i < 6; i++)    
25.     {    
26.         for(int j = cVal[i]; j <= n; j++)    
27.         {    
28.             // 若 目前面額 j 所需硬幣數大於 (目前面額 j 減去硬幣面額 cVal[i] 加 1 )    
29.             if( coin[j] > coin[j - cVal[i]] + 1 )    
30.                 coin[j] = coin[j - cVal[i]] + 1;    
31.         }    
32.     }    
33.     
34.     cout << coin[n] << endl;    
35.     return 0;    
36. }