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，很懷疑自己能不能做出來。后來發(fā)現(xiàn)這估計(jì)是WF里最水的那檔子難度了吧~不過拋開難度不說，WF的題目就是不同，做完仍有許多值得思考的地方，這個(gè)不算復(fù)雜的DP第一次交的時(shí)候700+ms，翻寫三遍后終于降到了35ms...
這道題目求所謂的“最大完美覆蓋”，為無遺漏的覆蓋完1-k面值的最大k值。很容易想到可以動(dòng)規(guī)，知道一個(gè)特定的面額i擁有組合方案后，基于i的一切可能的i+k面額都是一個(gè)新的組合，DP結(jié)束所有面額之后對表由0開始掃描即可，于是有了第一份最暴力的代碼，轉(zhuǎn)移方程為 dp[i][s][v]=(dp[i-1][s-k][v-k*w[i]])?1:0，k為窮舉前i-1種面額最多貼了s-k張，而i面值目前貼了k張，遞推共貼s張的方案，對每一個(gè)狀態(tài)s∈[0,MAXS]，單獨(dú)對k*w[i]做0/1背包，dp的空間復(fù)雜度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
}
但是很快發(fā)現(xiàn)這份代碼進(jìn)行了很多的冗余計(jì)算和額外的空間。首先增加[S]狀態(tài)進(jìn)行遞推是完全沒有必要的，我們的目的只是為了防止一個(gè)特定的面額i在使用了j張的時(shí)候，保證v-j*w[i]處的方案不會(huì)使用了太多的郵票，使得總數(shù)量大于給定的s。因此我們關(guān)鍵只是想知道一個(gè)特定的面值v到底使用了幾枚郵票，因此可以把狀態(tài)dp[i][s][v]改為dp[i][v][0]/ dp[i][v][1]，前者繼續(xù)做標(biāo)記，后者保存當(dāng)前面值使用了幾枚郵票。
更加順理成章的，既然每一個(gè)點(diǎn)的dp[i][v][1]我們都知道了，那么[i]狀態(tài)也是完全沒有必要的了，因?yàn)橐幻多]票貼不貼的唯一限制只是那個(gè)s，只要dp[i][v][1]<s，即使遞推dp[i][v]使用到了dp[i][v-k*w[i]]，程序也是正確的。于是得第二份程序，效率提升到110ms，時(shí)間復(fù)雜度仍為N*S*V，dp的空間復(fù)雜度降為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
接下來還能不能再優(yōu)化呢？我們對每一張郵票，先是遞推一張，再遞推兩張，三張……s張，事實(shí)上做了大量重復(fù)的工作，仍然是注意到那個(gè)最關(guān)鍵的狀態(tài)dp[v][1]，只要它存在，我們就知道了所有能知道的信息。聯(lián)系到無限背包的O(N*V)算法，很容易想到可以從v=0開始遞推單張郵票直到max_v，并且這個(gè)算法一定是正確的，只要時(shí)刻保證任意的dp[v][1]<=s。此外容易忽略的地方是，如果某個(gè)面值之前從未發(fā)現(xiàn)方案，明顯的dp[v][0]=1，dp[v][1]=dp[v-w[i]][1]+1 當(dāng)dp[v-w[i]][0]=1且dp[v-w[i]][1]+1<=s，但是當(dāng)多個(gè)可行的方案可以推出一個(gè)面值v時(shí)，我們應(yīng)取使得dp[v][1]最小的方案遞推過來，這樣才能保證求出的覆蓋是最優(yōu)覆蓋。此時(shí)算法的復(fù)雜度為N*V，已經(jīng)達(dá)到了理論下界。
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}
網(wǎng)上的許多分析認(rèn)為題目是一個(gè)多重背包，因?yàn)樗拗屏肃]票數(shù)s，但個(gè)人認(rèn)為這個(gè)并不是使之稱為多重背包的限制，因?yàn)檫@個(gè)s這是限制了放入的所有物品的總量，而不是特別的針對一種物品進(jìn)行限制，這也就決定了每一種物品的用量是互相限制但又是“相對無限”的，從而可以運(yùn)用無限背包的N*V算法求解。這道相對簡單的dp題目最大的啟示就是，對問題性質(zhì)進(jìn)行深入分析是獲得優(yōu)秀解法的必要前提。