alan23273850 的刷題筆記
d904: 換零錢
Tags: change-making
出處：https://zerojudge.tw/ShowProblem?problemid=d904
提交：https://zerojudge.tw/Submissions?problemid=d904&account=allllllan123456
問題：給你 $N\in[1,10]$ 個不同的正整數係數 $a_i$ 以及一個正整數 $C\in[1,1000]$，問你所有滿足方程式 $\displaystyle\sum_{i=1}^na_ix_i = C$ 的非負整數解之中 $\displaystyle\sum_{i=1}^nx_i$ 的最小值？
解法：此乃 change-making 問題，可參閱本站對於該問題的解析。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 int C, N, dp[1001]={1}; // important initial condition
6 while (cin >> C >> N) {
7 memset(dp, 0x7f, sizeof dp); dp[0] = 0;
8 while (N--) { int price; cin >> price;
9 for (int j=price; j<=C; j++)
10 if (dp[j-price] + 1 < dp[j])
11 dp[j] = dp[j-price] + 1;
12 }
13 cout << dp[C] << '\n';
14 }
15 return 0;
16}