最小郵票數

時間限制：1 秒

記憶體限制：32 兆

特殊判題：否

送出：1680

解決：558

題目描述：

有若幹張郵票，要求從中選取最少的郵票張數湊成一個給定的總值。

如，有1分，3分，3分，3分，4分五張郵票，要求湊成10分，則使用3張郵票：3分、3分、4分即可。

輸入：

有多組資料，對于每組資料，首先是要求湊成的郵票總值M，M100。然後是一個數N，N〈20，表示有N張郵票。接下來是N個正整數，分别表

示這N張郵票的面值，且以升序排列。

輸出：

對于每組資料，能夠湊成總值M的最少郵票張數。若無解，輸出0。

樣例輸入：

10

5

1 3 3 3 4

樣例輸出：

3

取最小滿足值的背包問題

#include<stdio.h>
#include<string.h>
#define INF 0x11111111
int a[],dp[];
int min(int n,int m)
{return n<m?n:m;}
int main()
{
    int i,j,n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
       for(i=;i<m;i++)
       scanf("%d",&a[i]);
       memset(dp,INF,sizeof(dp));
       dp[]=;
       for(i=;i<m;i++)
       {
          for(j=n;j>=a[i];j--)
          dp[j]=min(dp[j],dp[j-a[i]]+);
       }
       if(dp[n]>=)
       printf("0\n");
       else
       printf("%d\n",dp[n]);
    }
    return ;
}