題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b028。
此題用 Dynamic Programming 可參考網友 Chih-Yu Yeh 的說明文件:
- for(int i = 0; i < 6; i++)
- {
- for(int j = cVal[i]; j <= n; j++)
- {
- // 若 目前面額 j 所需硬幣數大於 (目前面額 j 減去硬幣面額 cVal[i] 加 1 )
- if( coin[j] > coin[j - cVal[i]] + 1 )
- coin[j] = coin[j - cVal[i]] + 1;
- }
- }
程式碼:
- /*
- *
- * coin[i] 目前面額 i 所需硬幣數
- *
- */
- #include <iostream>
- #include <cstring>
- using namespace std;
- int main()
- {
- int cVal[6] = {1, 5, 10, 12, 16, 20};
- int coin[101];
- // 將所需硬幣數全部設為100個
- memset(coin, 100, sizeof(coin));
- coin[0] = 0;
- int n;
- cin >> n;
- for(int i = 0; i < 6; i++)
- {
- for(int j = cVal[i]; j <= n; j++)
- {
- // 若 目前面額 j 所需硬幣數大於 (目前面額 j 減去硬幣面額 cVal[i] 加 1 )
- if( coin[j] > coin[j - cVal[i]] + 1 )
- coin[j] = coin[j - cVal[i]] + 1;
- }
- }
- cout << coin[n] << endl;
- return 0;
- }
沒有留言:
張貼留言