1     #include<stdio.h>
 2     #include<string.h>
 3     const int inf=0x3f3f3f3f;
 4     struct node
 5     {
 6         int v,c;
 7     };
 8     node sta[105];
 9     int dp[20010];
10     int dp2[20010];
11     int main()
12     {
13         int n,t,i,j,maxc,cnt=1;   //开始cnt赋值在while里面，娘希匹，错了10+
14         while(scanf("%d%d",&n,&t),n+t)
15         {
16             maxc=-inf;
17      
18             for(i=0;i<n;i++)
19             {
20               scanf("%d",&sta[i].v);
21               if(maxc<sta[i].v)      maxc=sta[i].v;
22             }
23             for(i=0;i<n;i++)
24                 scanf("%d",&sta[i].c);
25             maxc+=t;
26             for(i=1;i<=maxc+1;i++)
27                 dp[i]=inf;
28             dp[0]=0;
29             for(i=0;i<n;i++)
30             {
31                 if(sta[i].v*sta[i].c>=t) /*完全背包*/
32                 {
33                     for(j=sta[i].v ; j<=maxc ;j++)
34                     {
35                         if(dp[j]>dp[j-sta[i].v]+1)
36                             dp[j]=dp[j-sta[i].v]+1;
37                     }
38                 }
39                 else
40                 {
41                     int k=1;
42                     while(sta[i].c>k)
43                     {
44                         for( j=maxc ; j>=sta[i].v*k ; j-- )
45                         {
46                             if(dp[j]>dp[j-sta[i].v*k]+k)
47                                    dp[j]=dp[j-sta[i].v*k]+k;
48                         }
49                         sta[i].c-=k;
50                         k<<=1;
51                     }
52                         for( j=maxc; j>=sta[i].c*sta[i].v ; j-- )
53                         {
54                             if(dp[j]>dp[j-sta[i].v*sta[i].c]+sta[i].c)
55                                 dp[j]=dp[j-sta[i].v*sta[i].c]+sta[i].c;
56                         }
57                 }
58 
59             }
60             for(i=1;i<=maxc+1;i++)
61                 dp2[i]=inf;
62             dp2[0]=0;
63             for(i=0;i<n;i++)
64             {
65                 for(j=sta[i].v ;j<=maxc;j++)
66                 {
67                     if(dp2[j]>dp2[j-sta[i].v]+1)
68                           dp2[j]=dp2[j-sta[i].v]+1 ;
69                 }
70             }
71             int ans=inf;
72             for(i=t;i<=maxc ;i++)
73             {
74                if(ans>dp[i]+dp2[i-t])    ans=dp[i]+dp2[i-t];
75             }
76             if(ans==inf)  printf("Case %d: -1\n",cnt++);
77             else    
78                 printf("Case %d: %d\n",cnt++,ans);
79             
80 
81         }
82         return 0;
83     }

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int inf=0x3f3f3f3f;
 4 struct node
 5 {
 6     int v,c;
 7 };
 8 node sta[105];
 9 int dp[20010];
10 int dp2[20010];
11 int main()
12 {
13     int n,t,i,j,maxc,cnt=1;
14     while(scanf("%d%d",&n,&t),n+t)
15     {
16         maxc=-inf;
17         for(i=0;i<n;i++)
18         {
19           scanf("%d",&sta[i].v);
20           if(maxc<sta[i].v)      maxc=sta[i].v;
21         }
22         for(i=0;i<n;i++)
23             scanf("%d",&sta[i].c);
24         maxc+=t;
25         memset(dp,-1,sizeof(dp[0])*(maxc+1));
26         dp[0]=0;
27         for(i=0;i<n;i++)
28         {
29             if(sta[i].v*sta[i].c>=t) /*完全背包*/
30             {
31                 for(j=sta[i].v ; j<=maxc ;j++)
32                 {
33                     if(dp[j-sta[i].v]!=-1&&(dp[j]==-1||dp[j]>dp[j-sta[i].v]+1))
34                         dp[j]=dp[j-sta[i].v]+1;
35                 }
36             }
37             else
38             {
39                 int k=1;
40                 while(sta[i].c>k)
41                 {
42                     for( j=maxc ; j>=sta[i].v*k ; j-- )
43                     {
44                         if(dp[j-sta[i].v*k]!=-1&&(dp[j]==-1||dp[j]>dp[j-sta[i].v*k]+k))
45                                dp[j]=dp[j-sta[i].v*k]+k;
46                     }
47                     sta[i].c-=k;
48                     k<<=1;
49                 }
50                     for( j=maxc; j>=sta[i].c*sta[i].v ; j-- )
51                     {
52                         if(dp[j-sta[i].v*sta[i].c]!=-1&&(dp[j]==-1||dp[j]>dp[j-sta[i].v*sta[i].c]+sta[i].c))
53                             dp[j]=dp[j-sta[i].v*sta[i].c]+sta[i].c;
54                     }
55             }
56 
57         }
58         memset(dp2,-1,sizeof(dp2[0])*(maxc+1));
59         dp2[0]=0;
60         for(i=0;i<n;i++)
61         {
62             for(j=sta[i].v ;j<=maxc;j++)
63             {
64                 if(dp2[j-sta[i].v]!=-1&&(dp2[j]==-1||dp2[j]<dp2[j-sta[i].v]+1))
65                       dp2[j]=dp2[j-sta[i].v]+1 ;
66             }
67         }
68         int ans=inf;
69         for(i=t;i<=maxc ;i++)
70         {
71             if(dp2[i-t]!=-1&&dp[i]!=-1&&ans>dp[i]+dp2[i-t])
72                 ans=dp[i]+dp2[i-t];
73         }
74         if(ans==inf)  printf("Case %d: -1\n",cnt++);
75         else    
76         { 
77             printf("Case %d: %d\n",cnt++,ans);
78         }
79 
80     }
81     return 0;
82 }