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：
1
memset(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
9
void 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題目最大的啟示就是，對問題性質進行深入分析是獲得優秀解法的必要前提。