首页 > 代码库 > 题目1209:最小邮票数

题目1209:最小邮票数

最小邮票数

题目描述:

    有若干张邮票,要求从中选取最少的邮票张数凑成一个给定的总值。
    如,有1分,3分,3分,3分,4分五张邮票,要求凑成10分,则使用3张邮票:3分、3分、4分即可。

输入:

    有多组数据,对于每组数据,首先是要求凑成的邮票总值M,M<100。然后是一个数N,N〈20,表示有N张邮票。接下来是N个正整数,分别表示这N张邮票的面值,且以升序排列。

输出:

      对于每组数据,能够凑成总值M的最少邮票张数。若无解,输出0。

样例输入:
1051 3 3 3 4
样例输出:
3


Source Code:

#include <iostream>#define INF 0x7fffffff using namespace std; struct Stamp{    int weight;    int value;}; int dp[110];Stamp Arr[100000]; int minVal(int a,int b){    return a<b?a:b;} int main(){    int n,m;    while(cin>>n>>m){        for(int i=1;i<=m;++i){            cin>>Arr[i].weight;            Arr[i].value=1;        }        dp[0]=0;        for(int i=1;i<=n;++i)            dp[i]=INF;        for(int i=1;i<=m;++i){            for(int j=n;j>=Arr[i].weight;--j){                if(dp[j-Arr[i].weight]!=INF)                    dp[j]=minVal(dp[j],dp[j-Arr[i].weight]+Arr[i].value);            }        }        if(dp[n]==INF)            cout<<0<<endl;        else            cout<<dp[n]<<endl;    }    return 0;} /**************************************************************    Problem: 1209    User: lcyvino    Language: C++    Result: Accepted    Time:160 ms    Memory:2300 kb****************************************************************/

 

 

题目1209:最小邮票数