Description

Philatelists have collected stamps since long before postal workers were disgruntled. An excess of stamps may be bad news to a country's postal service, but good news to those that collect the excess stamps. The postal service works to minimize the number of stamps needed to provide seamless postage coverage. To this end you have been asked to write a program to assist the postal service.
Envelope size restricts the number of stamps that can be used on one envelope. For example, if 1 cent and 3 cent stamps are available and an envelope can accommodate 5 stamps, all postage from 1 to 13 cents can be "covered": 
            Number of   Number of

   Postage  1¢ Stamps	3¢ Stamps

      1         1           0

      2         2           0

      3         0           1

      4         1           1

      5         2           1

      6         0           2

      7         1           2

      8         2           2

      9         0           3

      10        1           3

      11        2           3

      12        0           4

      13        1           4

Although five 3 cent stamps yields an envelope with 15 cents postage, it is not possible to cover an envelope with 14 cents of stamps using at most five 1 and 3 cent stamps. Since the postal service wants maximal coverage without gaps, the maximal coverage is 13 cents.

      一开始看到这道题目的出处，World Final 95，很怀疑自己能不能做出来。后来发现这估计是WF里最水的那档子难度了吧~不过抛开难度不说，WF的题目就是不同，做完仍有许多值得思考的地方，这个不算复杂的DP第一次交的时候700+ms，翻写三遍后终于降到了35ms...

     这道题目求所谓的“最大完美覆盖”，为无遗漏的覆盖完1-k面值的最大k值。很容易想到可以动规，知道一个特定的面额i拥有组合方案后，基于i的一切可能的i+k面额都是一个新的组合，DP结束所有面额之后对表由0开始扫描即可，于是有了第一份最暴力的代码，转移方程为 dp[i][s][v]=(dp[i-1][s-k][v-k*w[i]])?1:0，k为穷举前i-1种面额最多贴了s-k张，而i面值目前贴了k张，递推共贴s张的方案，对每一个状态s∈[0,MAXS]，单独对k*w[i]做0/1背包，dp的空间复杂度N*S*MAXV：

 1memset(dp,0,sizeof(dp));
 2            
 3    for(i=0;i<=n;i++) for(j=0;j<=s;j++) dp[i][j][0]=1;
 4    for(i=1;i<=n;i++)
 5        for(j=0;j<=s;j++)
 6            for(k=0;k+j<=s;k++)
 7                 zeroOnePack(i,j,k,max_v);
 8                        
 9void zeroOnePack(int i,int j,int k,int max_v){
10    for(int v=max_v;v>=j*w[i];v--){
11        dp[i][k+j][v]=( dp[i-1][k][v-j*w[i]]|dp[i][k+j][v] )?1:0;
12    }
13}


       但是很快发现这份代码进行了很多的冗余计算和额外的空间。首先增加[S]状态进行递推是完全没有必要的，我们的目的只是为了防止一个特定的面额i在使用了j张的时候，保证v-j*w[i]处的方案不会使用了太多的邮票，使得总数量大于给定的s。因此我们关键只是想知道一个特定的面值v到底使用了几枚邮票，因此可以把状态dp[i][s][v]改为dp[i][v][0]/ dp[i][v][1]，前者继续做标记，后者保存当前面值使用了几枚邮票。
      更加顺理成章的，既然每一个点的dp[i][v][1]我们都知道了，那么[i]状态也是完全没有必要的了，因为一枚邮票贴不贴的唯一限制只是那个s，只要dp[i][v][1]<s，即使递推dp[i][v]使用到了dp[i][v-k*w[i]]，程序也是正确的。于是得第二份程序，效率提升到110ms，时间复杂度仍为N*S*V，dp的空间复杂度降为V：

 1memset(dp,0,sizeof(dp));
 2dp[0][0]=1;
 3            
 4for(i=1;i<=n;i++)
 5    for(j=0;j<=s;j++)
 6        zeroOnePack(i,j,s,max_v);
 7
 8void zeroOnePack(int i,int j,int s,int max_v){
 9    for(int v=max_v;v>=j*w[i];v--){
10       if( dp[v-j*w[i]][0] ){
11    
12          if( dp[v-j*w[i]][1]+j<=s & !dp[v][0] ){ dp[v][1]=dp[v-j*w[i]][1]+j; dp[v][0]=1; }
13    
14             if(dp[v-j*w[i]][1]+j<dp[v][1]) dp[v][1]=dp[v-j*w[i]][1]+j;
15    
16       }
17    }
18}
19


      接下来还能不能再优化呢？我们对每一张邮票，先是递推一张，再递推两张，三张……s张，事实上做了大量重复的工作，仍然是注意到那个最关键的状态dp[v][1]，只要它存在，我们就知道了所有能知道的信息。联系到无限背包的O(N*V)算法，很容易想到可以从v=0开始递推单张邮票直到max_v，并且这个算法一定是正确的，只要时刻保证任意的dp[v][1]<=s。此外容易忽略的地方是，如果某个面值之前从未发现方案，明显的dp[v][0]=1，dp[v][1]=dp[v-w[i]][1]+1 当dp[v-w[i]][0]=1且dp[v-w[i]][1]+1<=s，但是当多个可行的方案可以推出一个面值v时，我们应取使得dp[v][1]最小的方案递推过来，这样才能保证求出的覆盖是最优覆盖。此时算法的复杂度为N*V，已经达到了理论下界。

 1#include<cstdio>
 2#include<cstdlib>
 3#include<cstring>
 4#define V 1000
 5#define N 10
 6#define S 10
 7int dp[V+1][2];
 8int w[N+1];
 9int res[N+1];
10int maxCov,maxVal;
11
12void absPack(int i,int s,int max_v){
13    for(int v=w[i];v<=max_v;v++){
14       if( dp[v-w[i]][0] ){
15    
16          if( dp[v-w[i]][1]+1<=s && !dp[v][0] ){ dp[v][1]=dp[v-w[i]][1]+1; dp[v][0]=1; }
17    
18             if(dp[v-w[i]][1]+1<dp[v][1]) dp[v][1]=dp[v-w[i]][1]+1;
19
20       }
21    }
22}
23
24int main(){
25    int s,n,i,j,k,v,t,max_v,tmpVal;
26    while(scanf("%d",&s),s){
27        maxCov=maxVal=res[0]=-1;
28        scanf("%d",&t);
29        while(t--){
30            scanf("%d",&n);
31            for(tmpVal=i=1;i<=n;i++){ scanf("%d",&w[i]); tmpVal=(tmpVal<w[i])?w[i]:tmpVal; }
32            max_v=tmpVal*s;
33            memset(dp,0,sizeof(dp));
34            dp[0][0]=1;
35            
36            for(i=1;i<=n;i++) absPack(i,s,max_v);
37    
38            for(v=0;v<=max_v;v++) if(!dp[v][0]) break; --v;
39            
40            if(v>maxCov){
41                res[0]=n; for(i=1;i<=n;i++) res[i]=w[i]; maxCov=v; maxVal=tmpVal;
42            }else if(v==maxCov&&n<res[0]){
43                     res[0]=n; for(i=1;i<=n;i++) res[i]=w[i]; maxCov=v; maxVal=tmpVal;
44                  }else if(v==maxCov&&n==res[0]&&tmpVal<maxVal){
45                              res[0]=n; for(i=1;i<=n;i++) res[i]=w[i]; maxCov=v; maxVal=tmpVal;
46                          }else ; // print first
47            }
48            printf("max coverage = %d :",maxCov);
49            for(i=1;i<=res[0];i++) printf(" %d",res[i]);
50            printf("\n");
51
52    }
53    return 0;
54}


   网上的许多分析认为题目是一个多重背包，因为它限制了邮票数s，但个人认为这个并不是使之称为多重背包的限制，因为这个s这是限制了放入的所有物品的总量，而不是特别的针对一种物品进行限制，这也就决定了每一种物品的用量是互相限制但又是“相对无限”的，从而可以运用无限背包的N*V算法求解。这道相对简单的dp题目最大的启示就是，对问题性质进行深入分析是获得优秀解法的必要前提。