# The trouble of Xiaoqian

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1076    Accepted Submission(s): 355

Problem Description

In the country of ALPC , Xiaoqian is a very famous mathematician. She is immersed in calculate, and she want to use the minimum number of coins in every shopping. (The numbers of the shopping include the coins she gave the store and the store backed to her.) And now , Xiaoqian wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, ..., VN (1 ≤ Vi ≤ 120). Xiaoqian is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner .But Xiaoqian is a low-pitched girl , she wouldn’t like giving out more than 20000 once.

Input

There are several test cases in the input. Line 1: Two space-separated integers: N and T.  Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN)  Line 3: N space-separated integers, respectively C1, C2, ..., CN The end of the input is a double 0.

Output

Output one line for each test case like this ”Case X: Y” : X presents the Xth test case and Y presents the minimum number of coins . If it is impossible to pay and receive exact change, output -1.

Sample Input

3 70 5 25 50 5 2 1 0 0

Sample Output

Case 1: 3

多重背包.

``` 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 }```

657 篇文章64 人订阅

0 条评论

## 相关文章

### hdu 4315 Climbing the Hill（阶梯博弈转nim博弈）

Climbing the Hill Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/...

36211

### CodeForces 25C(Floyed 最短路)

F - Roads in Berland Time Limit:2000MS     Memory Limit:262144KB     64bit IO...

2374

### HDU 1695 GCD (欧拉函数，容斥原理)

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

2712

### HDU 5675 ztr loves math

ztr loves math Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65...

4106

### HDU 1013 Digital Roots【字符串，水】

Digital Roots Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

2774

Railroad Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

3525

30011

### HDUOJ------1711Number Sequence

Number Sequence Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/3...

3046

812

### HDU 3309 Roll The Cube(bfs)

Roll The Cube Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/327...

41513