Posted on 2010-08-02 15:24
Onway 阅读(275)
评论(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}