题目链接：

题意：

信封上最多贴S张邮票。有N个邮票集合，每个集合有不同的面值。问哪个集合的最大连续邮资最大，输出最大连续邮资和集合元素。最大连续邮资是用S张以内邮票面值凑1，2，3...到n+1凑不出来了，最大连续邮资就是n。如果不止一个集合结果相同，输出集合元素少的，如果仍相同，输出最大面值小的。

这个题意，刘汝佳的书上输出刚好写反。

 

分析：

先看一组数据。求最大连续邮资，那我想用二分啊，看这个答案是不是符合的，其实，在求这个答案是不是符合的，会重复计算，还不如按顺序计算。

这个从1开始算，算到某一个数，他的最少票数>s，就达到要求的了。那么这就是一个无穷背包问题了。

1 #include 
     
       2  3 using namespace std; 4  5 const int maxn = 25; 6 int a[maxn][maxn]; 7 int s,n; 8 int dp[1005]; 9 int ans[25];10 11 const int INF = 0x3f3f3f3f;12 13 int main()14 {15     while(scanf("%d",&s),s)16     {17         scanf("%d",&n);18         for(int i=0; i
      
       =0; k++)29                 {30                     dp[j] = min(dp[j],dp[j-a[i][k]]+1);31                 }32                 if(dp[j]>s)33                 {34                     ans[i] = j-1;35                     break;36                 }37             }38         }39 40         int anss = -1,cnt = 0;41         for(int i=0; i
       
        anss)44             {45                 anss = ans[i];46                 cnt = i;47             }48             else if(ans[i]==anss&&a[i][0]
        
         =0; j--)53                 {54                     if(a[i][j]
         
          a[cnt][j]) break;60                 }61                 if(ok) cnt = i;62             }63         }64         printf("max coverage =%4d :",anss);65         for(int i=1; i<=a[cnt][0]; i++)66             printf("%3d",a[cnt][i]);67         puts("");68     }69     return 0;70 }