题解 | #最小邮票数#

#include <iostream>
#include <vector>
using namespace std;

int stamp[21];
int minstamp = 500;
int n;

/*
    index 当前到了第几个邮票
    count 当前用了几张邮票
    m 剩余的总值
*/
void dfs(int index, int count, int m){
    if(m == 0){ //凑完了
        minstamp = min(minstamp, count);
        return;
    }
    if(index >= n){ //如果超出了邮票数量
        return;
    }
    if(m < 0){ //超出了总值
        return;
    }
    //选这张
    dfs(index + 1, count + 1, m - stamp[index]);
    //不选这张
    dfs(index + 1, count, m);
    return;
}


int main() {

    int m; //m为邮票总值  n为邮票数

    while (scanf("%d%d", &m, &n) != EOF) {
        for(int i = 0; i < n; i++){
            scanf("%d", &stamp[i]);
        }
        dfs(0, 0, m);
        if(minstamp == 500){ //无解
            printf("0\n");
        }else{
            printf("%d\n", minstamp);
        }
    }

}