台中女中程式解題系統: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. }  

沒有留言: