1 //题目1209：最小邮票数题目描述： 2 //有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 3 //如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。 4 #include "stdafx.h" 5 #pragma warning(disable:4996) 6 #include <iostream> 7 #include <stdio.h> 8 #include <cstring> 9 #include <algorithm>10 using namespace std;11 12 int v,N;13 int w[1000];14 int dp[1000];15 #define inf 100000016 int min(int a,int b)17 {18     return a>b?b:a;19 }20 void solve()21 {22     memset(dp,inf,sizeof(dp));23 24     dp[0] = 0;25     for (int i=1;i<=N;++i)//遍历物品26     {27         for (int j=v;j>=w[i];--j)//遍历体积,价值为1，也即邮票的张数，我们要取得最小的价值。28         {29             dp[j]=min(dp[j],dp[j-w[i]]+1);30         }31     }32     if(dp[v] >=1000)33         cout << 0 << endl;34     else35         cout << dp[v] << endl;36 }37 int main()38 {39     freopen("a.txt","r",stdin);40     while (cin>>v>>N)41     {42         for (int i=1;i<=N;++i)43         {44             scanf("%d",&w[i]);45         }46         solve();47     }48     return 0;49 }