思路
最简单的方法就是深搜了,就是逆序选择每一次可能选择的邮票。
#include<iostream> #include<vector> using namespace std; int getCnt(int m, vector<int>& stamps, int index, int cnt){ if(m == 0) return cnt; int ans = 20; //下一张邮票可能取 index ~ 0 中的某一张 for(int i = index; i >= 0; i --){ if(m == stamps[i]) ans = min(ans, cnt + 1); //如果邮票面额大于要凑齐的总值,自然不需要去选 if(m > stamps[i]){ int newCnt = getCnt(m - stamps[i], stamps, i - 1, cnt + 1); if(newCnt != 0){ ans = min(ans, newCnt); } } } return ans == 20 ? 0 : ans; } int main(){ int m, n; while(cin >> m >> n){ vector<int> stamps(n); for(int i = 0; i < n; i ++) cin >> stamps[i]; cout << getCnt(m, stamps, n - 1, 0) << endl; } }
当然,更好的方法应该是动态规划,这其实是一个背包问题,背包容量为 m,放邮票使得邮票数最少。定义一个二维数组dp,dp[i][j]表示用前i张邮票组成总值为j所需的最小邮票数。对于第i张邮票,其实我们只有两种选择啦,选或者是不选。那么选或者不选如何决定呢,这就要取决于怎样才能使得dp[i][j]的值最小啦。所以状态转移方程就是dp[i][j]=min(dp[i-1][j],dp[i-1][j-stamps[i]]+1)。
#include<iostream> #include<algorithm> #include<vector> using namespace std; const int MAX = 100000; int main() { int m, n; while (cin >> m >> n) { vector<int> stamps(n + 1, 0); vector<vector<int>> dp(n + 1, vector<int>(m + 1, MAX)); for(int i = 1; i <= n; i ++) cin >> stamps[i]; dp[0][0] = 0; for (int i = 1; i <= n; i ++) { for (int j = 0; j <= m; j ++) { if (j < stamps[i]) { dp[i][j] = dp[i - 1][j]; continue; } else { dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - stamps[i]] + 1); } } } if (dp[n][m] == MAX) cout << 0 << endl; else cout << dp[n][m] << endl; } return 0; }