题解 | #最小邮票数#

0-1背包变形：容量恰好用完

类比：容量：给定的总面值sum、邮票[i]的重量：面值w[i] 、价值：均为1

第i轮 dp[j]：前i张邮票凑出总面值为j的最少张数

• 初始状态：dp[0]=0; dp[i]=INF(0<i<=sum) 表示无法完成
• 递推关系：dp[j]=min(dp[j],dp[j-w[i]]+1)

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=101;
const int INF=0x7fffffff;
int w[maxn];

int dp[maxn];
int best(int sum,int n){
    
    dp[0]=0;//初始化
    for(int i=1;i<=sum;i++){
        dp[i]=INF;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=w[i];j--){//从后往前更新
             if(dp[j-w[i]]!=INF)dp[j]=min(dp[j],dp[j-w[i]]+1);//if避免加法上溢
        }
    }
    
    if(dp[sum]==INF)dp[sum]=0;
    return dp[sum];
}


int main(){
    int sum,n;
    while(scanf("%d%d",&sum,&n)!=EOF){
        for(int i=1;i<=n;i++)scanf("%d",&w[i]);
        printf("%d\n",best(sum,n));
    }
}