Posted on 2010-08-02 15:24
Onway 閱讀(315)
評論(0) 編輯 收藏 引用 所屬分類:
傷不起的ACM
pku 1882
題意：
給出多組由不同面值組成的郵票，求出由給出的那些面值能組成連續面額值最大的一組。（具體見原題，做完后發
現是95年的finals,呵呵）
剛看完背包九講的第二講完全背包，百度一下pku 完全背包，看到有說pku1882是一完全背包。按照完全背包去想，
寫出的代碼調了很久，然后越調發現越不像完全背包。完全背包里物品都有一個價值，物品個數不限，而在這個題
目里，都不滿足這兩個條件，可能我太水吧，但我真的不知道怎么能將這個題按完全背包去想。如果說有相似的話
，我覺得就是在狀態設計和遞推順序與完全背包是很相似的，可能吧，就是這個原因，就可以將這個DP分在完全背
包一類中。
思路：
假設郵票沒有張數限制，那么就很像完全背包了(ft!!)。然后對1到1000（最多是(91+92+……100)*10）的各種面額
進行枚舉。同時記錄每一種面額的最小張數。最后做一次統計，張數為0或是大于題目要求的都是不符合的面額。
枚舉的過程是很像完全背包是挺相似的說。
題目的測試數據里有一些毛病，在每一組郵票中，面值為1的郵票是一定出現了的。
1
#include <iostream>
2using namespace std;
3const int MAX=961;
4int dp[12][MAX];
5int data[12][12];
6int fmin(int a,int b)
7
{return a<b?a:b;}
8int main()
9{
10
int s;
11 while(scanf("%d",&s)&&s)
12
{
13 memset(dp,0,sizeof(dp));
14 int n,i,j,k;
15 scanf("%d",&n);
16 for(i=1;i<=n;++i)
17 {
18 scanf("%d",&data[i][0]);
19 for(j=1;j<=data[i][0];++j)
20 {
21 scanf("%d",&data[i][j]);
22 dp[i][data[i][j]]=1;
23
}
24 }
25
26 for(i=1;i<=n;++i)
27 for(j=1;j<=data[i][0];++j)
28 for(k=data[i][j]+1;k<=MAX-1;++k)
29 if(dp[i][k-data[i][j]]==0)
30 dp[i][k]=0;
31 else if(dp[i][k]==0)
32 dp[i][k]=dp[i][k-data[i][j]]+1;
33 else
34 dp[i][k]=fmin(dp[i][k],dp[i][k-data[i][j]]+1);
35
36 for(i=1;i<=n;++i)
37 {
38 for(j=1;j<=MAX-1;++j)
39 if(dp[i][j]==0||dp[i][j]>s)
40 break;
41 data[i][data[i][0]+1]=j-1;
42 }
43
44 k=1;
45 for(i=2;i<=n;++i)
46 if(data[i][data[i][0]+1]>data[k][data[k][0]+1])
47 k=i;
48 else if(data[k][data[k][0]+1]==data[i][data[i][0]+1]&&data[i][0]<data[k][0])
49 k=i;
50 else if(data[k][data[k][0]+1]==data[i][data[i][0]+1]&&data[k][0]==data[i][0]
51 &&data[i][data[i][0]]<data[k][data[k][0]])
52 k=i;
53
54 printf("max coverage = %d : ",data[k][data[k][0]+1]);
55 for(i=1;i<=data[k][0];++i)
56 printf("%d ",data[k][i]);
57 printf("\n");
58 }
59 return 0;
60
}
61
今天看了二維費用的背包才知道，原來這個題是屬于二維費用背包的。當然二維費用的背包，也是基于0-1背包或是完全背包的。
用二維費用的方法再寫了一次這個題，時間和內存都沒有上面那個好。
1#include <iostream>
2using namespace std;
3int d[12][12][1002];
4int test[12][13];
5int fmax(int a,int b)
6{return a>b?a:b;}
7int main()
8{
9 int s,n;
10 while(scanf("%d",&s)&&s)
11 {
12 scanf("%d",&n);
13 int i,j,k,l;
14 for(i=1;i<=n;++i)
15 {
16 scanf("%d",&test[i][0]);
17 for(j=1;j<=test[i][0];++j) scanf("%d",&test[i][j]);
18 }
19
20 memset(d,0,sizeof(d));
21 for(i=1;i<=n;++i)
22 {
23 for(j=1;j<=test[i][0];++j)
24 for(k=1;k<=s;++k)
25 for(l=test[i][j];l<=1000;++l)
26 d[i][k][l]=fmax(d[i][k][l],d[i][k-1][l-test[i][j]]+test[i][j]);
27 for(j=1;j<=1000;++j)
28 if(d[i][s][j]!=j)
29 break;
30 test[i][test[i][0]+1]=j-1;
31 }
32
33 k=1;
34 for(i=2;i<=n;++i)
35 if(test[i][test[i][0]+1]>test[k][test[k][0]+1])
36 k=i;
37 else if(test[i][test[i][0]+1]==test[k][test[k][0]+1]
38 &&test[i][0]<test[k][0])
39 k=i;
40 else if(test[i][test[i][0]+1]==test[k][test[k][0]+1]
41 &&test[i][0]==test[k][0]
42 &&test[i][test[i][0]]<test[k][test[k][0]])
43 k=i;
44
45 printf("max coverage = %d : ",test[k][test[k][0]+1]);
46 for(i=1;i<=test[k][0];++i)
47 printf("%d ",test[k][i]);
48 printf("\n");
49 }
50 return 0;
51}