台中女中程式解題系統：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. using namespace std;
9. int main()
10. {
11. int cVal[6] = {1, 5, 10, 12, 16, 20};
12. int coin[101];
13. // 將所需硬幣數全部設為100個
14. memset(coin, 100, sizeof(coin));
15. coin[0] = 0;
16. int n;
17. cin >> n;
18. for(int i = 0; i < 6; i++)
19. {
20. for(int j = cVal[i]; j <= n; j++)
21. {
22. // 若 目前面額 j 所需硬幣數大於 (目前面額 j 減去硬幣面額 cVal[i] 加 1 )
23. if( coin[j] > coin[j — cVal[i]] + 1 )
24. coin[j] = coin[j — cVal[i]] + 1;
25. }
26. }
27. cout << coin[n] << endl;
28. return 0;
29. }