计蒜客习题：凑数

---

问题描述

给出 n 种数，第 i 个数为ai，每种数能选任意多个，问你最少需要选多少个数使得选出来的数的和正好是 m。
输入格式
输入第一行两个整数 n(1≤n≤100),m(1≤m≤10^9)。
接下里一行输入n个数ai(1≤ai≤100)
输出格式
输出最少需要的数的个数（一种数选多少个就算多少个）。如果不能正好组成 m，输入”-1”。
样例输入
3 12
5 1 4
样例输出
3

---

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int dp[328400];
int arr[105];
int ans;
int main() {
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    int i;int mx=0;int j,k,tmp;
    scanf("%d%d",&n,&m);ans=m+100;
    for(i=1;i<=n;i++){
        scanf("%d",&arr[i]);
    }
    sort(arr+1,arr+n+1);
    n=unique(arr+1,arr+n+1)-arr-1;
    for(i=1;i<n;i++){
        for(j=arr[i]; j <= 100000; j++)
            dp[j] = min(dp[j],dp[j - arr[i]] + 1);
    }
    for(i=0;i<=min(100000,m);i++)if(dp[i]<=100000 && ((m-i)%arr[n]==0)){
        ans=min(ans,dp[i]+(m-i)/arr[n]);
    }
    if(ans>m){
        printf("-1");
    }else{
        printf("%d",ans);
    }
    return 0;
}