题解 | 最小邮票数

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXM=101;
const int MAXN=21;//M是总容量，N是数量

int main()
{
	int M,N;
	cin>>M;
	cin>>N;
	int value[MAXN];
    fill(value,value+MAXN,1);//注意千万不能通过int value[MAXN]={1}这种方式初始化，因为这种方式只是将第一个元素初始化为1 
	int price[MAXN];
	int dp[MAXM];//这里的dp[j]表示当要凑成的邮票总值为j时所需邮票的最小张数（当dp[j]仍为1000时说明无解） 
	fill(dp,dp+MAXM,1000);
    dp[0]=0;//表示当要凑成0总值时需要0张邮票，这是有意义的所以不能省，不然会报错！！！
	for(int i=1;i<=N;i++)
	{
		cin>>price[i];
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=M;j>=price[i];j--)
		{
			dp[j]=min(dp[j],dp[j-price[i]]+value[i]);
		}
	}
	if(dp[M]==1000)//说明没有这样的邮票选择方式，无解 
	{
		cout<<0<<endl;
	}
	else
	{
		cout<<dp[M]<<endl;
	}
	return 0; 
 }