题目描述
有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。
输入描述:
有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。
输出描述:
对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。
示例1
输入
10
5
1 3 3 3 4
输出
3
题目分析：
最少邮票数 >> 01动态规划
状态
集合中数字
dp[i][j] 0 1 2 3 4 5 6 7 8 9 10
1 0 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 3 0 1 ∞ 1 2 ∞ ∞ ∞ ∞ ∞ ∞
1 3 3 0 1 ∞ 1 2 ∞ 2 3 ∞ ∞ ∞
1 3 3 3 0 1 ∞ 1 2 ∞ 2 ∞ ∞ 3 4
1 3 3 3 4 0 1 ∞ 1 2 2 2 2 3 3 3
状态迁移方程
dp[j] = min{dp[j],dp[j-stamp[i]]+1}
其中dp[j-stamp[i]]+1，表示将第i个邮票加入集合后 凑总量为j的面额 所需要的最少邮票数量
代码：
#define INF 1000
int stamp[1000];
int dp[1000];
// 返回最少数量，num表示邮票的个数，deno表示要凑成的面额
int Min_Stamp(int num,int deno){
int i,j;
//将状态全部初始化为最多
for(j=0;j<=deno;++j){
dp[j]= (j==0)?0:INF;
}
for(i=0;i<num;i++){
//从后向前寻找若能凑成，且使数量变少就使用，不能也无所谓因为还是INF
for(j=deno;j>=stamp[i];j--){
if(dp[j-stamp[i]]!=INF)dp[j]=(dp[j] < dp[j-stamp[i]]+1)? dp[j]: dp[j-stamp[i]]+1;
}
}
return dp[deno]==INF?0:dp[deno];
}
int main()
{
int num,deno;
while(scanf("%d %d",&deno,&num)!=EOF){
for(int i=0;i<num;i++)scanf("%d",stamp+i);
printf("%d",Min_Stamp(num,deno));
}
return 0;
}