邮局发行一套票面有n(0＜n＜=10)种不同面值的邮票。若限每封信所贴的邮票张数不得超过m枚，存在整数r使得用不超过m(0＜m＜=2n)枚的邮票，可以贴出连续整数1，2，3，…，r值来，找出这种面值数，使得r值最大。
一行，输入N及M
输出R
2 3
7
按照题目的意思，由于要找出最大能拼出的数，因此要用一个函数dp(),来找出最大能拼出的数，然而要找出这个数，还需要找出这n种邮票分别为多少，所以还需要一个函数dfs(),这个函数用来找这n种邮票。
此时，我们可以用一个数组a[x]，来储存第x种邮票的面值为多少，同时，用一个数组f[i]表示要凑出总值为i的最少需要的邮票数，a[x]用于找下一个邮票面值，f[i]用于找当前情况下最大能组成的数值，即max(r)。
详细代码（附带每一步的解释）如下：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 int n,m,a[100],maxr,f[10000]; 7 void init() 8 { 9 cin>>n>>m; 10 a[1]=1; 11 } 12 int DP(int n) 13 { 14 int i,j; 15 f[0]=0; 16 for(i=1;;i++)//枚举总值 17 { 18 f[i]=-1;//f[i]存要凑出总值为i的最少需要的邮票数 19 for(j=1;j<=n;j++)//枚举邮票面值a[j] 20 if(i-a[j]>=0/*a[j]可以用来凑i*/ && f[i-a[j]]+1<=m/*加上后邮票数不超过m*/ &&(f[i]==-1 || f[i-a[j]]+1<=f[i])/*可以更新f[i]的值*/) 21 f[i]=f[i-a[j]]+1;//更新f[i]的值 22 if(f[i]==-1)//凑不出来 23 return i-1;// 24 } 25 } 26 void DFS(int p) 27 { 28 if(p>n)//如果面值大于i，那么就不能再往下dfs，已经到了更新答案的时候了 29 { 30 int s=DP(n);//n种邮票面值可以凑出的最大值 31 if(s>maxr) 32 { 33 maxr=s; 34 } 35 return; 36 } 37 int i;//如果还可以往下深搜 38 for(i=a[p-1]+1;i<=DP(p-1)+1;i++)//枚举可以新放的邮票的值，从a[p-1]->目前最大邮票单张面额，dp(p-1)+1->下一张最大单张邮票面额，也就是枚举a[p]可以有的值 39 { 40 a[p]=i;//更新此时a[p]的值 41 DFS(p+1);//对此时已有邮票的单张面额进行深搜，更新a[p+1]的值，或者更新maxr 42 } 43 } 44 45 int main() 46 { 47 48 init(); 49 DFS(2); 50 cout<<maxr<<endl; 51 }
原文：http://www.cnblogs.com/ly-Kirsty/p/6576266.html