台中女中程式解題系統：b029: 福袋!福袋!

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

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

此題用 Dynamic Programming，和 b028: 忙碌的超商店員很接近。

主要的想法為：目前的組合種類數等於 目前面額減去各硬幣面額之組合種類數的加總。

程式碼：

1. #include <iostream>  
2. #include <cstring>  
3.   
4. using namespace std;  
5.   
6. int main()  
7. {  
8.     int cVal[5] = {2, 5, 10, 20, 25};  
9.     int cnt[1001];  
10.   
11.     // 將所需組合種類數全部設為 0  
12.     memset(cnt, 0, sizeof(cnt));  
13.   
14.     cnt[0] = 1;  
15.     int n;  
16.   
17.     cin >> n;  
18.   
19.     for(int i = 0; i < 5; i++)  
20.     {  
21.         for(int j = cVal[i]; j <= n; j++)  
22.         {  
23.             // 目前的組合種類數等於 目前面額減去各硬幣面額之組合種類數的加總  
24.             cnt[j] += cnt[j - cVal[i]];  
25.         }  
26.     }  
27.   
28.     cout << cnt[n] << endl;  
29.     return 0;  
30. }