题解 | #最小邮票数#

#include<iostream>

using namespace std;

struct node {
    int price;
    int num;
};
int main(){
    
    int M,N;
    int value[21];
    value[0]=0;
    node dp[20][100];
    node n;
    n.price = 0;
    n.num = 0;
    for(int i=0;i<100;i++) dp[0][i] = n;
    for(int i=0;i<20;i++) dp[i][0] = n;
    
    while(cin>>M>>N){
        for(int i=1;i<=N;i++){
            cin>>value[i];
        }
        for(int i=1;i<=N;i++){
            for(int price=1;price<=M;price++){
                node doNothing = dp[i-1][price];
                
                    node last = dp[i-1][price-value[i]];
                    node selectIt;
                    selectIt.num = last.num+1;
                    selectIt.price = last.price+value[i];
                    if(selectIt.price<=price){
                        if(price-selectIt.price<price-doNothing.price){//选择以后更接近j，则选择
                            dp[i][price] = selectIt;
                        } else if(price-selectIt.price>price-doNothing.price){//否则不选
                            dp[i][price] = doNothing;
                        } else if(selectIt.num<doNothing.num){//如果选不选price都一样，则选num更小的
                            dp[i][price] = selectIt;
                        } else {
                            dp[i][price] = doNothing;
                        }
                    } else {
                        dp[i][price] = doNothing;
                    }
                
            }
        }
        int num = dp[N][M].num;
        if(dp[N][M].price==M){
            cout<<dp[N][M].num<<endl;
        } else {
            cout<<0<<endl;
        }
    }
    
    return 0;
}