凑成邮票总值的最少张

总值的最少张"/>

凑成邮票总值的最少张

题目描述

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

输入描述:

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

输出描述:

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

输入例子:

10
5
1 3 3 3 4

输出例子:

3

【代码】 //背包问题

1. #include<algorithm>
2. #define min(a,b) a<b?a:b
3. using namespace std;
4. 
   
5. int main()
6. {  
7.   int dp[1000], a[1000];
8.   int sum, n;
9. 
   
10.   while(cin>>sum>>n)   
11.   {
12.     for(int i=0; i<1000; i++)
13.          dp[i] = 99999999;
14.  
15.     for(int i=0; i<n; i++)
16.          cin>>a[i];
17. 
    
18.       dp[0]=0;
19.      for(int i=0; i<n; i++)
20.        for(int j=sum; j>=a[i]; j--)
21.             dp[j] = min(dp[j], dp[j-a[i]] + 1);
22.  
23.      if(dp[sum] >= 1000)
24.         cout<<0<<endl;
25.      else
26.       cout<<dp[sum]<<endl;
27.  
28.      }
29.  return 0;
30. }