# 3.1.6 Stamps 邮票

3.1.6 Stamps 邮票

6 = 3 + 3
7 = 3 + 3 + 1
8 = 3 + 3 + 1 + 1
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1
11 = 3 + 3 + 3 + 1 + 1
12 = 3 + 3 + 3 + 3
13 = 3 + 3 + 3 + 3 + 1。

``````5 2
1 3``````

``````13
``````

``````# include<stdio.h>//DP,多重背包
# define M 9999999
int sign[55],f[2000005];
int min(int a,int b)
{
return (a<b?a:b);
}
int main()
{
int num,n,i,j;
scanf("%d %d",&num,&n);
for(i=0;i<n;i++)
scanf("%d",&sign[i]);
f[0]=0;
for(i=1;;i++)
{
f[i]=M;
for(j=0;j<n;j++)
if(sign[j]<=i)
f[i] = min(f[i],f[i-sign[j]]+1);
if(f[i]>num)//如果最小的数目都超过了num，那这个i就一定贴不出
break;
}
printf("%d\n",i-1);
return 0;
}``````

``````#include<iostream>
#include<cstring>
using namespace std;
#define MAX 2000002
int ans[MAX];
int num[51];
int main()
{
int k,n,i,j,big;
cin>>k>>n;
big=0;
for(i=0;i<n;i++)
{
cin>>num[i];
if(num[i]>big)big=num[i];
}
if(big==1)
{
cout<<k<<endl;
return 0;
}
memset(ans,1,sizeof(ans));
ans[0]=0;
for(i=1;i<=k;i++)
ans[i*big]=i;
for(i=1;i<=MAX;i++)
{
if(i%big==0)continue;
for(j=0;j<n;j++)
if(i-num[j]>=0)
if(ans[i-num[j]]+1<ans[i])ans[i]=ans[i-num[j]]+1;
if(ans[i]>k)break;
}
cout<<i-1<<endl;
return 0;
}

``````