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

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

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

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

主要的演算法如下:
  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. }   

沒有留言: