题解 | #最小邮票数#

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int main() {
    int sum;
    while (cin >> sum) {
        int N, data;
        cin >> N;
        int num = N;
        //dp[i]表示要凑i最少需要几张邮票
        vector<int> dp(100, 100);
        dp[0] = 0;//初始化，0元需要0张
        while (num--) {
            cin >> data;
            v.push_back(data);
        //    dp[data] = 1;(这儿不能这样初始化，会导致有些邮票被重复用)
        }
//先遍历物品，再遍历背包
//物品是正序的只有一遍遍历，比如要得到3，结果1，2选择完了，不可能再出现2，1
//属于【组合问题】
//先遍历背包，再遍历物品
//物品会有多次遍历，比如要得到3，结果1，2选择完了还可能会出现2，1的情况
//属于【排列问题】
//此题应属于组合问题
        for (int j = 0; j < N; j++) {//先遍历物品，就是邮票面值
            for (int i=sum;i>=0;i--)//后遍历背包，也就是要凑的邮票总值
                if (i >= v[j]) {
                    //dp[i]是不选择v[j]面值的邮票后最少需要的邮票数目
                    //dp[i - v[j]] + 1是选择v[j]面值的邮票后最少需要的邮票数目，选择了所以加1，同时要凑的目标小了所以是i - v[j]
                    dp[i] = min(dp[i], dp[i - v[j]] + 1);
                }
        }
        //for(int i=0;i<=sum;i++) cout<<dp[i]<<" ";
        //如果没有被更新，依旧是100的初值，说明无解
        if (dp[sum] == 100) {
            cout << "0";
        } else cout << dp[sum] << endl;
    }
}