最小邮票数

思路

最简单的方法就是深搜了，就是逆序选择每一次可能选择的邮票。

#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;
}